the 2-approximation for metric TSP

The travelling salesman problem (TSP) asks for the shortest tour that visits every city exactly once and returns home. In general it is brutally hard, but in the METRIC version distances obey the triangle inequality — going directly from A to C is never longer than detouring through B. This single, very natural assumption (true of straight-line and road distances) is enough to unlock a clean 2-approximation built on a minimum spanning tree.

The recipe in four steps. First, build a minimum spanning tree (MST) of the cities — the cheapest set of roads that connects them all. Second, imagine walking the tree by doubling every edge, which creates a closed walk that traverses each edge twice and visits every city; its length is exactly 2 * (MST weight). Third, this walk repeats cities, so 'shortcut' it: as you trace the walk, skip any city you have already visited and jump straight to the next new one. By the triangle inequality, every shortcut can only shorten the trip. The result is a genuine tour, and its length is at most the doubled walk, i.e. at most 2 * MST. The final link is the lower bound: any tour, including the optimal one, contains a path visiting all cities, and deleting one edge of the optimal tour leaves a spanning tree, so MST <= OPT. Chaining it: tour length <= 2 * MST <= 2 * OPT.

So the MST does double duty: it builds the solution AND certifies the bound, the recurring surrogate-for-OPT pattern. This is the textbook entry point to TSP approximation because every step is elementary — MST, doubling, shortcutting, triangle inequality. The honest caveats: the triangle inequality is essential (for general, non-metric TSP no constant-factor approximation exists at all unless P = NP), and the factor 2 is not the best known — Christofides improves it to 1.5 by replacing the wasteful edge-doubling with a smarter matching. Still, this 2-approximation is the conceptual foundation everyone learns first.