Proof Of Christofides' Three-Halves Guarantee

The Three Cost Contributions

Christofides’ algorithm combines three ideas: a minimum spanning tree, a matching of the tree’s odd-degree vertices, and shortcutting an Euler circuit. The key to its guarantee is to compare each of the first two costs with an optimal traveling-salesperson tour, then show that the final shortcutting step does not increase cost.

Throughout, let \(G=(V,E)\) be the complete graph on \(n\ge 3\) vertices. Each edge \(uv\) has a cost \(c(uv)\), where costs are positive, symmetric, and satisfy the triangle inequality: \(c(uv)\le c(uw)+c(wv)\) for any vertices \(u,v,w\). A tour visits each vertex exactly once and returns to its starting vertex. Its cost is the sum of the costs of its edges. Write \(\mathrm{OPT}\) for the minimum cost of a tour. Positivity and finiteness ensure that an optimal tour exists and has positive cost.

A spanning tree is a connected, cycle-free subgraph containing every vertex. A perfect matching on \(O\) is a set of pairwise vertex-disjoint edges that covers every vertex in \(O\); when \(O=\varnothing\), it is the empty matching of cost zero. The multigraph formed by adding matching edges may have parallel edges, which are kept as distinct copies when constructing its Euler circuit.

Two Bounds from an Optimal Tour

Proof. Remove any one edge from an optimal tour. The remaining edges form a spanning path: the vertices are still connected, and deleting one edge from the cycle creates no cycle. Thus they form a spanning tree. Since the removed edge has positive cost, this tree costs less than \(\mathrm{OPT}\). A minimum spanning tree costs no more than any spanning tree, so \(c(T)\le\mathrm{OPT}\). \(\square\)

Proof. The sum of the degrees in a tree is twice its number of edges, so the number of odd-degree vertices is even. If \(O=\varnothing\), the empty matching costs zero and the bound holds. Otherwise, write \(O=\{v_1,\ldots,v_k\}\), where \(k\) is even, in the order in which these vertices occur on an optimal tour. Replace each segment of that tour from one \(O\)-vertex to the next by the direct edge between its endpoints. Repeated application of the triangle inequality shows that each replacement costs no more than its segment. The resulting cyclic list of \(k\) edges therefore has total cost at most \(\mathrm{OPT}\). Divide its edges alternately into two groups. Each group pairs all \(k\) vertices, so each is a perfect matching; when \(k=2\), regard the two cyclic edges as separate copies, and either group is a one-edge matching. The two matching costs add to at most \(\mathrm{OPT}\), so at least one is at most \(\mathrm{OPT}/2\). A minimum-weight perfect matching costs no more than that matching. \(\square\)

The two lemmas apply to different objects. The first compares a spanning tree with a tour; the second uses the order of the tree’s odd-degree vertices on a tour to find an inexpensive matching. The matching need not consist of edges from the optimal tour.

Why the Added Multigraph Has an Euler Circuit

Every connected finite multigraph in which all degrees are even has an Euler circuit: a closed trail using every edge exactly once. Here, connectedness comes from the spanning tree, and adding an edge at each endpoint of a matching preserves even degree at every vertex. The following argument justifies the Euler-circuit step used by the algorithm.

Proof. Start at a vertex incident with an edge and follow unused edges until no further unused edge can be taken. The resulting trail must end where it started. If it ended at a different vertex, the number of used edges incident with that endpoint would be odd: every earlier visit pairs an arrival with a departure, but the final arrival has no departure. Since the vertex’s total degree is even, it would then have an unused incident edge, contradicting that the trail cannot be extended. We have obtained a closed trail.

If this trail does not use every edge, connectedness gives a vertex on the trail incident with an unused edge: along a path from the trail to an unused edge, take the first edge that leaves the set of vertices already on the trail. After removing the edges of a closed trail, every remaining degree is still even, because the trail used an even number of incident edges at each vertex. Starting at the vertex with an unused edge and repeating the trail construction therefore gives another closed trail of unused edges. Insert that trail into the first one at their common vertex. This makes a longer closed trail. Repeating this process must terminate because the multigraph has finitely many edges, and at termination the closed trail uses every edge. \(\square\)

In Christofides’ multigraph, each tree vertex has even degree after the matching is added. Indeed, a vertex in \(O\) gains exactly one incident matching edge, changing odd degree to even; every other vertex gains none and was already even. The tree connects all vertices, so the multigraph is connected and the lemma applies.

Shortcutting and the Guarantee

Proof. Let \(W\) be an Euler circuit of the multigraph formed from \(T\) and \(M\). Read the vertices in the order they occur in \(W\), keep only their first occurrences, and then return from the last retained vertex to the starting vertex. Every vertex appears in the resulting list exactly once, so it defines a tour.

For each two consecutive retained vertices, the portion of \(W\) between them is a walk. The triangle inequality, applied successively along that walk, says that the direct edge between its endpoints costs no more than the walk. The same applies to the final portion of \(W\) back to the starting vertex. These portions partition the edges of \(W\), so the shortcut tour costs no more than \(W\). Its cost is therefore at most \(c(T)+c(M)\). By the two lemmas, \(c(T)\le\mathrm{OPT}\) and \(c(M)\le\mathrm{OPT}/2\). Consequently its cost is at most \(\mathrm{OPT}+\mathrm{OPT}/2=3\mathrm{OPT}/2\). \(\square\)

A Common Pitfall

The alternating-edge argument does not show that both candidate matchings individually cost at most half the optimal-tour cost. It shows that their costs add to at most that amount before division by two, so the cheaper one is at most half.

For a concrete check, take \(V=\{a,b,c,d\}\) with every pair as an edge and positions \(0,1,2,3\), with cost equal to absolute difference. The tour \(a,b,c,d,a\) has edge costs \(1,1,1,3\), so costs \(6\). It is optimal: a closed tour must cross each of the three gaps at least twice, giving cost at least \(2(1+1+1)=6\). Alternating the four tour edges gives matchings \(ab,cd\), of cost \(1+1=2\), and \(bc,da\), of cost \(1+3=4\). The second costs \(4>6/2=3\), but the first costs \(2\le3\), as required. The minimum matching, not every matching, is what the proof bounds.

The guarantee is a worst-case upper bound, not a claim that every output costs exactly \(3\mathrm{OPT}/2\). The examples show why the separate estimates matter: the tree and matching costs may be below their respective bounds, and shortcutting may preserve or reduce the Euler-circuit cost.