Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 42 / 3 / c

Let $C^{\ast }$ be an optimal metric tour. Removing any one of its edges gives a spanning tree, so the minimum spanning tree $T$ satisfies $c(T)\le c(C^{\ast })$. The handshaking lemma shows that its odd-degree set $U$ has even size.

Follow $C^{\ast }$ and retain only vertices of $U$, shortcutting between consecutive retained vertices. This produces a cyclic order on $U$ of total cost at most $c(C^{\ast })$. If $U$ is nonempty, the alternating edges of that cyclic order form two perfect matchings; their costs sum to the cycle cost. One has cost at most $c(C^{\ast })/2$, so a minimum-weight perfect matching $M$ hasFor $|U|=2$, count the same undirected edge twice in the cyclic order; each alternating matching consists of one copy. For $U=\varnothing$, use the empty matching.

The multigraph with edges $T\uplus M$ is connected because it contains $T$. Each odd-degree vertex receives exactly one matching edge, and the other degrees are unchanged, so every degree is even. It therefore has an Euler circuit. Constructively, follow unused edges until returning to the starting vertex; parity prevents getting stuck elsewhere. If unused edges remain, connectivity supplies a vertex of the current circuit incident with one, and its additional closed trail can be spliced into the circuit. Repetition gives a circuit using every edge exactly once, including parallel copies.

Shortcut repeated vertices of this Euler circuit to obtain a metric tour. Its cost is at mostComputing a minimum spanning tree, a minimum-weight perfect matching, an Euler circuit and the shortcut tour is polynomial-time; weighted perfect matching is a standard polynomial-time graph optimization problem. Thus the Christofides algorithm is a $3/2$-approximation algorithm for symmetric metric tours.