All subjects · Mathematics · WDM11 (D1)

TSP lower bound: residual minimum spanning tree

A lower bound for the travelling salesman problem comes from deleting one vertex, finding a minimum spanning tree of the rest, and reconnecting the deleted vertex.

The method

1. Remove a vertex X and all its edges.

2. Find a minimum spanning tree of the remaining vertices (the residual MST), usually by Prim's algorithm.

3. Add the two shortest edges from X.

The total is a lower bound for the optimal tour.

Why it works

Any tour, with X removed, becomes a path through the other vertices, which is a spanning tree of them and so is at least the residual MST. The two tour edges at X are at least the two shortest edges at X.

Best lower bound

Removing different vertices gives different lower bounds. The best lower bound is the largest. If the residual tree plus the two edges forms a tour (a single cycle through every vertex), that tour is optimal.

Combining bounds

Write the answer as an interval, for example 57 ≤ d ≤ 62. If the best lower bound equals the best upper bound, the optimum has been found.

Worked example

Find a lower bound for table T by deleting A.

  1. Residual MST of B, C, D, E: weight 30
  2. Two shortest edges from A: 12, 15
  3. Lower bound = 30 + 12 + 15 = 57

Answer: 57

Key idea: Delete a vertex, residual MST of the rest, add the two shortest edges at the deleted vertex; keep the largest lower bound.

Check yourself

  1. Find the lower bound for table T obtained by deleting B.
    Show answer

    57. Residual MST of A, C, D, E: 35. Two shortest from B: 10, 12. Total 57.

  2. Deleting C from table T, what is the weight of the residual minimum spanning tree?
    Show answer

    37. MST of A, B, D, E has weight 37.

  3. Find the lower bound for table T obtained by deleting C.
    Show answer

    56. 37 + 9 + 10 = 56.

  4. Lower bounds for table T are found by deleting each vertex in turn. What is the best lower bound?
    Show answer

    57. Bounds: delete A: 57; delete B: 57; delete C: 56; delete D: 56; delete E: 56. Best (largest) 57.

  5. For table T the best upper bound is 62 and the best lower bound is 57. Which statement is correct?
    • 57 ≤ optimal tour length ≤ 62
    • The optimal tour length is 57
    • The optimal tour length is between 62 and 84
    • No conclusion is possible
    Show answer

    57 ≤ optimal tour length ≤ 62. The optimum lies between the best lower bound and the best upper bound.

  6. Why is the largest lower bound the best one?
    • It is always equal to the optimal value
    • It uses the most edges
    • It is closest to the optimal value while still never exceeding it
    • It comes from deleting the vertex with the most edges
    Show answer

    It is closest to the optimal value while still never exceeding it. Every lower bound is at most the optimum, so the largest narrows the interval the most.

  7. When does a residual minimum spanning tree lower bound prove that a tour is optimal?
    • When the residual tree plus the two edges forms a tour
    • When the deleted vertex has the shortest edges
    • When the lower bound is a whole number
    • When the residual tree has n - 2 edges
    Show answer

    When the residual tree plus the two edges forms a tour. If the structure is itself a tour, a real tour has the length of a lower bound, so it must be optimal.

Practise with instant feedback

Sources

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