From a Spanning Tree to a TSP Tour
A minimum spanning tree connects all cities at low cost, but it is not usually a tour: it has no cycle, and some vertices may have degree greater than two. Christofides’ algorithm turns such a tree into a tour in two stages. First it adds edges to make every degree even, so that an Euler tour is possible. Then it removes repeated vertices from that Euler tour by shortcutting. The triangle inequality ensures that shortcutting does not increase the cost.
Positivity matters: the weights define a metric on distinct vertices only if \(w(uv)>0\) whenever \(u\ne v\). The triangle inequality is the property needed for shortcutting. A minimum spanning tree is a spanning tree of least total weight. A perfect matching on a vertex set pairs all its vertices, with each vertex in exactly one pair; a minimum-weight perfect matching has the least total edge weight among those pairings.
The Algorithm and Why Its Steps Work
Choose any minimum spanning tree \(T\) of the weighted complete graph. Let \(O\) be the set of vertices whose degrees in \(T\) are odd. Find a minimum-weight perfect matching on \(O\), and add its edges to \(T\). For this step, regard the result as a multigraph: if a matching edge is already a tree edge, the added edge is a second, parallel copy. Find an Euler tour of this connected multigraph, then shortcut repeated vertices to obtain a Hamiltonian tour.
Proof. The sum of the degrees in a finite graph is twice the number of edges, because each edge contributes one to the degree at each endpoint. Thus the number of odd-degree vertices is even: a sum of degrees that is even cannot contain an odd number of odd summands. In particular, \(|O|\) is even. Pair the vertices of \(O\) arbitrarily; completeness guarantees that every pair is an edge, so this gives a perfect matching. At a vertex in \(O\), adding one matching edge increases its odd degree by one, making it even. At a vertex outside \(O\), the matching adds no incident edge, so its degree remains even. \(\square\)
The augmented multigraph is connected because it contains the spanning tree. A connected multigraph in which all degrees are even has an Euler tour: a closed trail that uses every edge exactly once. For completeness, here is the argument that gives the needed existence result.
Proof. Start at any vertex and extend a trail without reusing an edge until no unused incident edge is available at its endpoint. If the endpoint differed from the starting vertex, the used edges would contribute an odd number of incidences there: every visit other than the final arrival contributes incidences in pairs, and the final arrival contributes one. Since its total degree is even, it would still have an unused incident edge. This contradicts the stopping rule. The trail therefore closes. If it has not used every edge, connectedness gives a vertex on the closed trail incident with an unused edge: along a path from an unused edge to the vertices of the trail, take the first edge that reaches a vertex on the trail. The unused edges have even degree at every vertex, because removing a closed trail removes an even number of incidences at each vertex. Starting at the vertex with an unused incident edge and repeating the trail-extension argument produces another closed trail of unused edges. Insert that closed trail into the first one at their shared vertex. Each insertion uses at least one new edge, so after finitely many insertions the resulting closed trail uses every edge exactly once. \(\square\)
To shortcut, record the vertices in the order of their first appearance in the Euler tour, and then return from the last recorded vertex to the start. Each stretch of the Euler tour between consecutive recorded vertices is replaced by a direct edge; the final stretch back to the start is treated in the same way. Repeated application of the triangle inequality says the direct edge costs no more than the stretch it replaces. The recorded vertices are distinct, and the Euler tour traverses the spanning tree, so every vertex is recorded. The result is therefore a Hamiltonian tour with cost no greater than the Euler tour’s cost.
Worked Examples
Worked Example: A Four-Vertex Metric with Strict Shortcutting
Let \(V=\{A,B,C,D\}\). Set \(w(Ax)=1\) for \(x\in\{B,C,D\}\), and set the weight between any two distinct vertices in \(\{B,C,D\}\) to \(1.5\). These rules specify all six edges of the complete graph. The weights are positive and symmetric. A center-to-leaf distance is at most the sum of the other two distances through a third vertex, since \(1\le 1+1.5\); a leaf-to-leaf distance satisfies \(1.5\le 1+1\), and also \(1.5\le1.5+1.5\). Thus the triangle inequalities hold.
Tree and odd vertices. Choose the star \(T\) with edges \(AB,AC,AD\). Each edge has weight \(1\), so \(w(T)=1+1+1=3\). Every edge in the complete graph has weight at least \(1\); a spanning tree on four vertices has three edges, so no spanning tree can cost less than \(3\). The star is minimum. Its degrees are \(3,1,1,1\), so \(O=\{A,B,C,D\}\).
Matching and Euler tour. The three possible pairings of \(O\) have costs \(w(AB)+w(CD)=1+1.5=2.5\), \(w(AC)+w(BD)=1+1.5=2.5\), and \(w(AD)+w(BC)=1+1.5=2.5\). Hence each is minimum. Choose \(AB,CD\); the matching cost is \(2.5\). The edge \(AB\) is added as a parallel copy of the tree edge. The resulting degrees at \(A,B,C,D\) are \(4,2,2,2\).
| Stage | Edges or walk | Cost |
|---|---|---|
| Tree | \(AB,AC,AD\) | \(1+1+1=3\) |
| Matching added | copy of \(AB\), and \(CD\) | \(1+1.5=2.5\) |
| Euler tour | \(A,B,A,C,D,A\) | \(1+1+1+1.5+1=5.5\) |
| Shortcut tour | \(A,B,C,D,A\) | \(1+1.5+1.5+1=5\) |
The Euler walk uses the tree edge \(AB\) on its first traversal and its matching copy on its return from \(B\); it then uses \(AC,CD,DA\). Shortcutting the repeated \(A\) replaces the segment \(B,A,C\), of cost \(1+1=2\), by \(BC\), of cost \(1.5\). The tour visits all four vertices once before returning to \(A\). Its cost \(5\) is no greater than the Euler-tour cost \(5.5\), as required.
Worked Example: A Line Metric on Five Vertices
Let \(V=\{p_0,p_1,p_3,p_6,p_{10}\}\), with \(w(p_i p_j)=|i-j|\) for distinct indices. This defines positive symmetric weights. For any three distinct indices \(i,j,k\), \(|i-j|\le |i-k|+|k-j|\), so the weights satisfy the triangle inequality.
Choose the path tree with edges \(p_0p_1,p_1p_3,p_3p_6,p_6p_{10}\). Their weights are \(1,2,3,4\), giving total \(1+2+3+4=10\). This tree is minimum: for each of the four gaps \((0,1),(1,3),(3,6),(6,10)\), any spanning tree must have an edge crossing the cut between the vertices at or to the left of the gap and those to its right. The weight of an edge crossing several gaps is the sum of their lengths. Summing across the four cuts therefore gives a lower bound of \(1+2+3+4=10\) on every spanning tree’s weight, and the displayed path attains it.
The path endpoints \(p_0,p_{10}\) have degree \(1\); its other vertices have degree \(2\). Thus \(O=\{p_0,p_{10}\}\), whose only perfect matching is \(p_0p_{10}\), of weight \(|10-0|=10\). Adding that edge gives every vertex even degree. One Euler tour is \(p_0,p_1,p_3,p_6,p_{10},p_0\). It already visits every vertex once before returning to the start, so shortcutting changes nothing.
| Stage | Calculation | Cost |
|---|---|---|
| Tree | \(|1-0|+|3-1|+|6-3|+|10-6|\) | \(1+2+3+4=10\) |
| Matching | \(|10-0|\) | \(10\) |
| Euler and Hamiltonian tour | Path edges plus \(p_{10}p_0\) | \(10+10=20\) |
Check: the tour uses five edges with weights \(1,2,3,4,10\), so its cost is \(1+2+3+4+10=20\). The edge list visits \(p_0,p_1,p_3,p_6,p_{10}\) once each before returning to \(p_0\).
Worked Example: A Square Metric
Let \(V=\{A,B,C,D\}\), with edge weights \(w(AB)=w(BC)=w(CD)=w(DA)=1\) and \(w(AC)=w(BD)=2\). These are the Manhattan distances between the points \(A=(0,0)\), \(B=(1,0)\), \(C=(1,1)\), and \(D=(0,1)\). They are positive and symmetric, and the triangle inequality follows by applying \(|x_1-y_1|\le |x_1-z_1|+|z_1-y_1|\) and the corresponding inequality for the second coordinate, then adding.
Take \(T\) with edges \(AB,BC,CD\), of total weight \(1+1+1=3\). A spanning tree on four vertices has three edges, and every edge here has weight at least \(1\), so this tree is minimum. The degrees are \(1,2,2,1\), hence \(O=\{A,D\}\). The only perfect matching on \(O\) is \(AD\), of weight \(1\). After adding it, the multigraph has the Euler tour \(A,B,C,D,A\). It is already a Hamiltonian tour, with cost \(1+1+1+1=4\).
Check: the tree contributes \(3\), the matching contributes \(1\), and the Euler tour uses those four edge copies, for total \(3+1=4\). In this example there are no repeated vertices to shortcut.
What the Construction Guarantees—and a Common Pitfall
The construction always produces a Hamiltonian tour on a metric instance: the matching makes degrees even, the tree keeps the augmented multigraph connected, the Euler-tour argument supplies a closed traversal, and shortcutting produces a tour without increasing its cost. These steps describe the algorithm’s output, not by themselves a bound comparing that cost with an optimal TSP tour.
A common error is to treat the augmented object as a simple graph and discard a matching edge whenever it duplicates a tree edge. In the four-vertex example, the tree edge \(AB\) and its matching copy are distinct edge copies. Counting both gives degrees \(4\) at \(A\) and \(2\) at \(B\) after that matching edge is added. If the duplicate is discarded, the degrees remain \(3\) and \(1\), respectively, and the claimed even-degree condition fails. The Euler-tour step relies on the multigraph with both copies present.
Another error is to shortcut without the metric hypothesis. Replacing a segment \(u,\ldots,v\) by \(uv\) is justified because repeated triangle inequalities give \(w(uv)\) no larger than the segment’s total weight. Without the triangle inequality, that replacement can cost more, so this argument would not establish a non-increasing cost.
Check Your Understanding
For each question, use the definitions and justify any cost comparison.
- Why must a minimum spanning tree have an even number of odd-degree vertices?
- In the four-vertex example, what goes wrong with the Euler-tour condition if the matching copy of \(AB\) is discarded?
- For the five-vertex line metric, list the odd-degree vertices and the cost of their minimum-weight perfect matching.
- Explain why the shortcut from \(B,A,C\) to \(B,C\) in the first example does not increase cost.
- Which assumptions ensure that every matching pair is an available edge and that shortcutting does not increase tour cost?