Double-tree shortcutting is a 2-approximation for metric TSP

The complete graph on the vertex set of the instance, with the given lengths, is a finite connected real edge-weighted graph: the vertex set is nonempty because $n\ge 3$, and any two distinct vertices are adjacent, hence joined by the one-edge path consisting of that edge. All edge lengths are nonnegative rationals by the metric convention.

Run Kruskal's algorithm on this weighted graph, breaking ties by a fixed order of the finitely many edges. By [F4] it outputs a minimum spanning tree $T$. This run is polynomial time on the explicit rational input: there are at most $\mathrm{\mid }E\mathrm{\mid }$ additions, and each round can scan all edges, test eligibility by graph search, and compare the encoded rational lengths using polynomial bit arithmetic. By [F2], $T$ has minimum total weight among spanning trees.

Double every edge of $T$, obtaining the connected multigraph in which every vertex degree is twice its degrees in $T$, hence even; take an Euler circuit of this multigraph and shortcut repeated vertices in first-visit order. By [F6] the result is a Hamiltonian tour of the instance whose cost is at most $2w(T)$, and the doubling, traversal and first-visit scan take polynomial time in the size of the explicit graph.

The same tree $T$ is a minimum spanning tree of the complete weighted graph, so [F5] gives the lower bound $w(T)\le {\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$.

The tour returned in step 3.1 is feasible and has cost at most $2w(T)\le 2{\mathrm{OPT}}_{\mathrm{T}\mathrm{S}\mathrm{P}}$ by step 3.2. The algorithm is deterministic polynomial time by steps 2.1 and 3.1, with all ties resolved by fixed finite orders. By [F7] it is a polynomial-time $2$-approximation for metric TSP.