= Solution
Let $C^*$ be an optimal metric tour. Removing any one of its edges gives a <spanning tree>, so the <minimum spanning tree> $T$ satisfies $c(T)\leq c(C^*)$. The <handshaking lemma> shows that its odd-degree set $U$ has even size.
Follow $C^*$ 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^*)$. 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^*)/2$, so a <minimum-weight perfect matching> $M$ has
$$
\boxed{c(M)\leq\tfrac12c(C^*).}
$$
For $|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 most
$$
\boxed{c(T)+c(M)\leq\tfrac32c(C^*).}
$$
Computing 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 \b[the <Christofides algorithm> is a $3/2$-<approximation algorithm> for symmetric metric tours].
Back to article page
