The Odd-Vertex Matching Bound In Christofides Algorithm

Why the Odd Vertices Matter

In Christofides’ algorithm, a spanning tree is augmented by a perfect matching on the tree’s odd-degree vertices. The matching links are chosen using the metric costs, not necessarily from the tree. A key bound is that a minimum-cost such matching costs at most half the cost of an optimal tour. The reason is that an optimal tour can be shortcut to a cycle through the odd vertices, and alternating links around that cycle give two candidate matchings.

We work with a finite metric TSP instance on a vertex set \(V\) with \(|V|\geq 3\). It is represented by the complete undirected graph on \(V\), with edge costs \(d(u,v)\). The costs are symmetric, are positive for distinct vertices, and satisfy the triangle inequality \(d(u,w)\leq d(u,v)+d(v,w)\). A tour visits every vertex exactly once and returns to its starting vertex; its cost is the sum of its edge costs. An optimal tour is a tour of minimum cost, denoted \(\operatorname{OPT}\). Such a tour exists because there are finitely many tours.

The tree itself determines which vertices must be matched; the metric determines the cost of the matching edges. The bound below does not require the matching edges to belong to \(T\).

Why Alternating Links Give Matchings

The number of odd-degree vertices in a tree is even. Indeed, each tree edge contributes one to the degree of each of its two endpoints, so the sum of all degrees is twice the number of tree edges and is even. A sum of integers is even only if it contains an even number of odd summands. Thus we can write \(|O(T)|=k\) with \(k\) even.

List the odd vertices in the order in which they appear while travelling around an optimal tour: \(u_1,u_2,\ldots,u_k\). Between each consecutive pair in this cyclic order, follow the tour until reaching the next odd vertex. These portions of the tour partition the tour’s edges. Replace each portion by a single metric edge joining its endpoints. The triangle inequality says the cost of each replacement edge is no greater than the cost of the portion it replaces. Consequently, the sum of the costs of these cyclic links is at most \(\operatorname{OPT}\).

There are two ways to take alternating links: pair \(u_1\) with \(u_2\), \(u_3\) with \(u_4\), and so on; or pair \(u_2\) with \(u_3\), \(u_4\) with \(u_5\), and so on, finally pairing \(u_k\) with \(u_1\). Since \(k\) is even, each choice uses every odd vertex exactly once. Both choices are perfect matchings. Their costs add up to the cost of all the cyclic links, so at least one of them costs no more than half that sum.

Proof. Write the odd vertices in their order on an optimal tour as \(u_1,\ldots,u_k\), where \(k\) is even. If \(k=0\), the empty matching has cost zero, which is at most \(\operatorname{OPT}/2\). Now suppose \(k\geq 2\). For \(1\leq i\leq k\), let \(c_i=d(u_i,u_{i+1})\), with \(u_{k+1}=u_1\). Each link \(u_i u_{i+1}\) shortcuts the portion of the optimal tour from \(u_i\) to \(u_{i+1}\) in the chosen direction. Repeated application of the triangle inequality shows that \(c_i\) is at most the cost of that portion: for a portion with successive vertices \(x_0,\ldots,x_r\), induction on \(r\) gives \(d(x_0,x_r)\leq\sum_{j=1}^{r}d(x_{j-1},x_j)\). The portions partition the tour, so \(\sum_{i=1}^{k}c_i\leq\operatorname{OPT}\).

One matching consists of the links in positions \(1,3,\ldots,k-1\); the other consists of the links in positions \(2,4,\ldots,k\). Each is a perfect matching because these pairs partition the vertices \(u_1,\ldots,u_k\). Their costs sum to \(\sum_{i=1}^{k}c_i\), so the lesser of the two costs is at most \(\frac12\sum_{i=1}^{k}c_i\), and hence at most \(\operatorname{OPT}/2\). The minimum-cost perfect matching costs no more than either candidate matching, proving the result. When \(k=2\), the two indexed cyclic links have the same pair of endpoints, but each alternating choice is still a perfect matching with one edge; the cost-sum argument remains valid. \(\square\)

This argument proves a bound on the minimum matching by exhibiting candidate matchings. It does not require computing the minimum matching or finding the optimal tour in order to justify the inequality. The tour is a comparison object in the proof.

A Common Pitfall

It is not valid to claim that each alternating matching costs at most half the cyclic-link sum. The proof only guarantees that at least one does: the two costs add to the sum, so their minimum is at most half. In the first example, the cyclic-link sum is \(1+1+2+4=8\), and half of it is \(8/2=4\). One alternating matching costs \(1+2=3\), but the other costs \(1+4=5\), which is greater than \(4\). The correction is to compare both alternating choices and select the cheaper one. The minimum perfect matching costs no more than that selected candidate.

The factor of one-half comes from having two complementary matchings, not from the fact that either matching uses half of the links. A matching does use half the link positions, but the individual link costs need not be equal. The argument relies on the sum of the two matching costs, not on an assumption that costs are evenly distributed.

How the Bound Fits the Algorithm

The matching bound applies to every spanning tree \(T\) on the metric instance: its odd-degree set determines the vertices to pair, and the optimal tour supplies the cyclic order used in the proof. The proof then provides two feasible matchings whose combined cost is at most the optimal tour cost. It follows that the cheaper candidate, and therefore the minimum perfect matching, costs at most half of \(\operatorname{OPT}\).

This is the matching-cost estimate used in the analysis of Christofides’ algorithm. The estimate alone does not prove a bound on the algorithm’s full tour: it concerns only the matching added to the tree. Combining it with the spanning-tree cost bound and the tour construction is a separate step.