TSP upper bound: doubling the minimum spanning tree

Doubling the tree

Find a minimum spanning tree. Walking along every edge of the tree twice visits every vertex and returns to the start, so 2 × (weight of MST) is the length of a closed route: an upper bound.

Short cuts

The doubled walk revisits vertices. Replace a section that goes back through visited vertices by a direct edge to the next unvisited vertex (or back to the start). By the triangle inequality this never makes the route longer. Each short cut gives a better (smaller) upper bound.

Writing it

State the walk, for example A B C D E D C B A = 2 × 42 = 84, then the short cut: replace E D C B A (11 + 9 + 10 + 12) by EA (20), giving 62. Name the edges used.

Worked example

Find an upper bound for the tour of table T using the minimum spanning tree method with a short cut.

1. Minimum spanning tree (Prim from A): AB, BC, CD, DE, weight 42
2. Doubled: A B C D E D C B A, length 84
3. Short cut: replace E D C B A (11 + 9 + 10 + 12) by EA (20)

Answer: Upper bound 62 from tour ABCDEA

Check yourself

1. Find the weight of the minimum spanning tree for table T.
   Show answer

   42. Edges AB (12), BC (10), CD (9), DE (11); total 42.

2. Find the initial upper bound for table T given by doubling the minimum spanning tree.
   Show answer

   84. 2 × 42 = 84.

3. Improve the upper bound for table T by replacing the section E D C B A of the doubled walk with the direct edge EA.
   Show answer

   62. 84 - (11 + 9 + 10 + 12) + 20 = 62.

4. Why does a short cut never increase the length of a route in the classical problem?
   • Short cuts always use the shortest edge
   • The tree has no cycles
   • The doubled walk is always optimal
   • The triangle inequality makes a direct edge no longer than a route through other vertices
   Show answer

   The triangle inequality makes a direct edge no longer than a route through other vertices. Direct is never longer than via other vertices when the triangle inequality holds.

5. Why is twice the weight of a minimum spanning tree an upper bound for the travelling salesman problem?
   • No tour can be shorter than the tree
   • Walking every tree edge there and back gives a closed route through every vertex
   • The tree is a tour
   • It is always the optimal length
   Show answer

   Walking every tree edge there and back gives a closed route through every vertex. Any closed route visiting every vertex has length at least the optimum, so its length is an upper bound.

6. The optimal tour for table T has length 62. By how much does the doubled-tree bound exceed it?
   Show answer

   22. 84 - 62 = 22. Doubling alone is a poor bound, which is why short cuts are needed.

Practise with instant feedback Print this lesson

Sources

• Pearson Edexcel International Advanced Level in Mathematics specification (issue 3)
• Pearson Edexcel IAL Decision Mathematics 1 scheme of work

Last updated 7 November 2026. Spotted a mistake? Tell us.