A minimum spanning tree lower-bounds metric-TSP optimum

Take an optimal tour and write its cyclic ordering as $v_1,v_2,\dots ,v_n$ with the closing edge $\{v_n,v_1\}$, so ${\sum }_{i=1}^{n-1}d(v_i,v_{i+1})+d(v_n,v_1)={\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$. Delete the closing edge and let $Q$ be the subgraph of $K$ with vertex set $V$ and edge set $\{v_1{v}_2,v_2{v}_3,\dots ,v_{n-1}{v}_n\}$. The subgraph $Q$ spans $V$ and is connected: for $i<j$ the walk $v_i,v_{i-1},\dots ,v_1,v_2,\dots ,v_j$ lies in $Q$ and joins $v_i$ to $v_j$. Its total length is $w(Q)={\sum }_{i=1}^{n-1}d(v_i,v_{i+1})={\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}-d(v_n,v_1)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$, because lengths are nonnegative.

Since $Q$ is a finite connected graph, [F3] provides a spanning tree $S$ of $Q$ with $V(S)=V$ and $E(S)\subseteq E(Q)$. All lengths are nonnegative, so deleting edges cannot increase total length and $w(S)={\sum }_{e\in E(S)}d(e)\le {\sum }_{e\in E(Q)}d(e)=w(Q)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$. In particular $S$ is also a spanning tree of the complete graph $K$, since $E(S)\subseteq E(Q)\subseteq E(K)$ and $V(S)=V$.

The tree $T$ is a minimum spanning tree of the complete graph $K$, and $S$ is a spanning tree of $K$, so by [F2] $w(T)\le w(S)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$.

Therefore every metric-TSP instance satisfies $w(T)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$ for a minimum spanning tree $T$ of its complete weighted graph. The argument uses one optimal tour only as a comparison object; it computes no optimal tour and gives a lower bound on ${\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$, not an upper bound.