# Approximated TSP: weight of minimum spanning tree less than cost of the optimal tour?

In the chapter, Approximation Algorithms of Introduction to Algorithm, 3rd Edition, for the approximation problem Travelling Salesman Problem, the author proposes a approximation method that first constructs a minimum spanning tree.

In order to prove this algorithm is a 2-approximation algorithm, the author claims that:

The weight of the minimum spanning tree $T$ is less than the cost of the optimal tour.

I am wondering if the minimum spanning tree(which is acyclic) of $G$ ensures that its weight is necessarily smaller than any tour(which is cyclic) of the same graph $G$

PS:

The original claim is:

## 1 Answer

If you take any tour and remove any edge, then you get a spanning tree. Hence the weight of a minimum spanning tree is at most the weight of every tour.

I should add that one of the tricks behind this algorithm is that while we can't find a minimum tour efficiently, we can find a minimum spanning tree. Minimum spanning tree is an efficiently computable relaxation of minimum Hamiltonian path.