How Does the Deleted Vertex Algorithm Estimate a Lower Bound for the Travelling Salesman Problem?

The deleted vertex algorithm estimates a lower bound by deleting one vertex, finding a minimum spanning tree (MST) for the remaining vertices, and then adding the two smallest edges connecting the deleted vertex to the graph. The resulting total cannot exceed the weight of the optimal travelling salesman cycle.

Why the algorithm works

In the travelling salesman problem (TSP), a valid tour is a Hamiltonian cycle: it visits every vertex exactly once before returning to the starting vertex. Therefore, exactly two tour edges meet each vertex.

Suppose vertex $A$ is deleted from an optimal tour, together with its two incident edges. What remains is a path connecting all the other vertices, which is also a spanning tree. Its weight must be at least the weight of the MST on those vertices, because the MST is the cheapest possible spanning tree.

The two tour edges originally incident to $A$ must also cost at least as much as the two cheapest available edges incident to $A$. Therefore,

$$L_A = \text{MST weight after deleting } A + \text{two smallest edge weights incident to } A$$

is a valid lower bound.

For example, if the MST weighs $31$, and the two smallest edges incident to $A$ weigh $6$ and $8$, then

$$L_A = 31 + 6 + 8 = 45.$$

The optimal tour must therefore have weight at least $45$. Repeat the process for different deleted vertices; the largest valid lower bound is the most useful estimate.

IB exam technique

This is AHL 3.16, so it is HL-only and may appear in a GDC-active Paper 1, Paper 2, or Paper 3 question. Show the deleted vertex, MST edges and weight, two restored edge weights, and final bound. Do not claim that the lower bound is the optimal tour unless a matching upper bound has also been found.