Spanning-Tree Lower Bounds For TSP

Why a Spanning Tree Bounds a TSP Tour

A TSP tour must visit every vertex and return to its starting point. A spanning tree must connect every vertex, but it does not need to contain a cycle. This difference gives a useful lower bound: remove one edge from any tour, and what remains is a spanning tree. Since a minimum spanning tree is no heavier than any other spanning tree, its weight cannot exceed the tour’s weight, provided edge weights are nonnegative.

Throughout, a TSP instance is a complete, undirected, finite graph \(G=(V,E)\) with \(n=|V|\ge 3\) and a nonnegative weight \(w(e)\) on each edge \(e\). Completeness ensures that a tour exists. A tour is a Hamiltonian cycle: a cycle that visits every vertex exactly once. For an edge set \(F\), write \(w(F)=\sum_{e\in F}w(e)\). A spanning tree is a connected, acyclic subgraph containing every vertex. A minimum spanning tree (MST) is a spanning tree of minimum total weight; its weight is denoted \(w(\mathrm{MST})\). There are finitely many spanning trees, so an MST exists.

Proof. Let \(C\) be any TSP tour, and choose any edge \(e\) of \(C\). Removing \(e\) from the cycle leaves a path that contains every vertex, so the remaining edges form a spanning tree \(T\). By the definition of a minimum spanning tree, \(w(\mathrm{MST})\le w(T)\). Also, \(w(C)=w(T)+w(e)\), and \(w(e)\ge0\) by assumption. Therefore \(w(\mathrm{MST})\le w(T)\le w(C)\). Since this holds for every tour, it holds for an optimal tour. \(\square\)

The nonnegative-weight assumption matters for the last inequality: if a tour edge had negative weight, removing it could increase the weight. The bound does not require the triangle inequality. It applies to any complete instance with nonnegative weights, including instances that are not metric.

Finding and Certifying the MST

For the examples, we use Kruskal’s algorithm. List the edges in nondecreasing order of weight, then scan the list and accept an edge exactly when adding it does not create a cycle with the edges already accepted. Stop when the accepted edges connect all vertices. Ties can be resolved in any order.

Proof. Let \(F\) be the accepted edges so far. They form a forest: the empty set has no cycle, and an edge is accepted only if it creates no cycle. We show that after every accepted edge, there is some MST containing all the edges accepted so far. Initially this holds because a connected finite graph has a spanning tree of minimum weight.

Suppose the algorithm accepts an edge \(e=uv\), and the current forest is \(F\). The endpoints \(u,v\) lie in different components of \(F\). Let \(S\) be the vertex set of the component containing \(u\). The edge \(e\) crosses the cut between \(S\) and \(V\setminus S\). No edge crossing this cut has weight less than \(w(e)\): any such edge would have been considered earlier. If it had been accepted, its endpoints would now be connected in \(F\), contrary to crossing between two components. If it had been rejected, its endpoints were already connected by accepted edges at the time of rejection, and those edges remain in \(F\), giving the same contradiction. Thus \(e\) is a minimum-weight edge crossing this cut.

By the induction assumption, take an MST \(T\) containing \(F\). If \(e\in T\), it already contains the enlarged accepted set. If \(e\notin T\), adding \(e\) to \(T\) creates a cycle: the unique path in \(T\) from \(u\) to \(v\), together with \(e\), is that cycle. The path must cross from \(S\) to \(V\setminus S\); choose one such edge \(f\). Since \(T\) contains \(F\), and no edge of \(F\) crosses between components of \(F\), \(f\notin F\). Also \(w(f)\ge w(e)\), because \(e\) is a minimum-weight edge crossing the cut. Removing \(f\) from the cycle gives a spanning tree \(T'\) containing \(F\) and \(e\), with \(w(T')=w(T)-w(f)+w(e)\le w(T)\). Since \(T\) is minimum, \(T'\) is also an MST. This proves the induction step.

When the algorithm stops, its accepted edges connect all vertices; otherwise, connectedness of the graph supplies an edge between two different forest components, and the algorithm would accept it. The accepted edges are therefore a connected forest, hence a spanning tree. The induction argument gives an MST containing that tree. Both are spanning trees, so the contained tree is the same tree; consequently, the algorithm’s output is an MST. \(\square\)

This proof also explains why cycle checks are essential. A spanning tree on \(n\) vertices has \(n-1\) edges; accepting an edge that closes a cycle cannot help connect new vertices and may prevent the chosen set from being a tree.

Worked Calculations

Common Pitfall and Use of the Bound

Do not select the cheapest \(n-1\) edges without checking for cycles. In the third example, the three cheapest edges are \(AB\), \(AC\), and \(BC\), with total weight \(1+2+2=5\). They form a triangle and leave \(D\) isolated, so they are not a spanning tree. Calling \(5\) the MST weight would give an invalid certificate. Kruskal’s algorithm rejects \(BC\) and instead includes \(BD\), giving the connected tree of weight \(1+2+3=6\).

The MST bound is a benchmark, not usually an exact TSP solution. Every tour is a spanning tree plus one additional edge, but the extra edge must complete a Hamiltonian cycle, so it cannot in general be chosen independently of the tree. The bound remains useful because it is simple to compute and applies without needing to know an optimal tour. In particular, a proposed tour whose weight is below \(w(\mathrm{MST})\) cannot be valid for the stated instance: either its cost, the MST computation, or the instance data must be wrong.