eduKate Sengkang

Small Group Tutorials

Here to help students catch up, keep up, and move ahead. Book a consultation here.

Chat on WhatsApp

How to Learn Christofides’ Algorithm: Metric TSP, Minimum Spanning Trees, Odd-Vertex Matching and the 3/2 Approximation

Quick Read. Christofides’ algorithm is one of the best teaching examples of approximation with a proof. The beginner should first understand the travelling salesman problem, metric distances and why an arbitrary nearest-neighbour tour can be bad. The intermediate learner should combine a minimum spanning tree, minimum-weight perfect matching on odd-degree vertices, an Euler tour and shortcutting. The advanced learner should prove the 3/2 guarantee using two lower bounds on the optimum tour. The professional should distinguish metric symmetric TSP from general, asymmetric or non-metric routing problems, understand the matching bottleneck, and know when a theoretical approximation guarantee is more valuable than an empirically strong heuristic without the same guarantee.

One-sentence answer

Christofides’ algorithm builds a cheap connected structure, repairs its odd degrees with a minimum-weight perfect matching, traverses the resulting Eulerian multigraph, and shortcuts repeated vertices to obtain a metric-TSP tour whose cost is at most 3/2 of optimal.

First: what problem is being solved?

In the symmetric metric travelling salesman problem, we are given a complete undirected weighted graph. Edge weights are nonnegative, symmetric and satisfy the triangle inequality: going directly from u to w is never more expensive than going from u to v to w.

The goal is a minimum-cost Hamiltonian cycle: visit every vertex exactly once and return to the start. The exact TSP is NP-hard, so polynomial-time algorithms are not expected to always find the optimum. An approximation algorithm instead promises a tour within a provable factor of optimum.

Level 1 — Beginner: start from a spanning tree

Any Hamiltonian cycle becomes a spanning tree if one edge is removed. Therefore the minimum spanning tree T cannot cost more than the optimum TSP tour OPT:

w(T) ≤ OPT

This is our first lower bound. It is also the first algorithm-design move: solve an easier relaxation of the hard problem, then repair what the relaxed solution is missing.

Why the tree is not already a tour

A tree connects every vertex cheaply, but many vertices may have odd degree. Euler’s theorem tells us that a connected multigraph has an Euler circuit exactly when every vertex has even degree. So the next task is parity repair.

A basic graph fact now becomes algorithmically decisive: every graph has an even number of odd-degree vertices. Let O be the set of odd-degree vertices in the MST.

Level 2 — Intermediate: repair parity with matching

Compute a minimum-weight perfect matching M on the vertices in O. Adding those matching edges to the MST changes every odd degree by one, so all degrees become even. The result is a connected Eulerian multigraph.

T = minimum_spanning_tree(G)
O = vertices of odd degree in T
M = minimum_weight_perfect_matching(G[O])
H = multigraph(T + M)
E = Euler_tour(H)
C = shortcut_repeated_vertices(E)
return C

There are four distinct subproblems here: minimum spanning tree, parity identification, minimum-weight perfect matching and Euler traversal. The algorithm is therefore a composition of mature primitives rather than one monolithic trick.

Shortcutting is where metricity matters

The Euler circuit may visit vertices many times. To turn it into a Hamiltonian cycle, skip a vertex when it has already been visited and go directly to the next new vertex. By the triangle inequality, replacing a path u→v→w with the direct edge u→w cannot increase cost.

This step is invalid as a guarantee if the edge weights are non-metric. A shortcut could then be more expensive than the path it replaces. The triangle inequality is not a cosmetic assumption; it is one of the proof’s structural supports.

A hand-worked example

Place six points in the plane and use Euclidean distance. First draw the MST. Mark every odd-degree vertex. If four vertices are odd, compare the possible perfect matchings among those four and choose the minimum-cost one. Add those edges to the tree. Trace an Euler circuit through the resulting multigraph, then shortcut repeated vertices.

The learning objective is not to memorise the final route. It is to explain the job of each layer: the tree gives cheap connectivity, the matching repairs parity, the Euler circuit uses every selected edge, and shortcutting converts edge traversal into vertex visitation.

Level 3 — Advanced: where the 3/2 comes from

We already know w(T) ≤ OPT. The second bound is on the matching. Consider an optimal TSP tour and look only at the vertices O that are odd in the MST. Walking around the optimal tour induces two alternating pairings of those vertices whose total cost, after metric shortcutting, is at most OPT. Therefore at least one of those pairings costs at most OPT/2, and the minimum-weight perfect matching M cannot cost more than that:

w(M) ≤ OPT / 2

So the Eulerian multigraph has weight

w(T) + w(M) ≤ OPT + OPT/2 = 3OPT/2.

Shortcutting does not increase weight, giving the 3/2 approximation guarantee.

Why this proof is more important than the recipe

The recipe can be copied in a few lines. The proof teaches the reusable idea: construct a solution whose cost decomposes into parts, then bound each part by a fraction of an unknown optimum using relaxations or structural properties.

That is approximation-algorithm thinking. You do not need to know OPT numerically. You need lower bounds that OPT must satisfy.

Christofides is not “the TSP algorithm”

The guarantee applies to complete undirected metric TSP. Real routing problems may include one-way streets, time windows, capacities, depots, forbidden turns, service times, asymmetric costs or distances that do not satisfy triangle inequality. Those are different optimisation models.

A professional system should therefore identify the mathematical contract before selecting the algorithm. Applying a famous guarantee outside its assumptions is worse than using a simpler method whose limitations are understood.

Metric closure for incomplete graphs

Practical graph libraries often allow an incomplete connected network by first replacing each pair of required vertices with the length of a shortest path between them. This creates a complete metric closure. NetworkX’s travelling_salesman_problem documentation describes this approach before applying an approximation routine such as Christofides for undirected graphs.

After obtaining a tour in the closure, the algorithm expands each closure edge back into its original shortest path. This may revisit intermediate network vertices, which is acceptable for a route through required stops but is not the same object as a Hamiltonian cycle in the original sparse graph.

The matching step is the heavyweight component

MST and Euler-tour computation are efficient and familiar. Minimum-weight perfect matching on a general graph is the more sophisticated subroutine. Classical implementations use blossom-based matching algorithms, and its cost often dominates a straightforward Christofides implementation.

This matters when teaching complexity. The total algorithm is not just “four linear-looking steps.” Its practical and asymptotic cost inherits the complexity of the matching routine used.

Approximation guarantee versus empirical quality

Local-search methods such as 2-opt and Lin–Kernighan-style heuristics can often produce excellent tours in practice. Christofides’ special value is different: it offers a worst-case certificate. These are complementary notions of quality.

A common professional pattern is to use a guaranteed construction as a reliable starting point or bound, then improve the tour with local search while retaining the knowledge that the initial solution already had a theoretical floor.

Professional implementation decisions

  • Metric validation: know whether symmetry and triangle inequality actually hold.
  • Graph completion: distinguish a true complete metric instance from a metric closure of a sparse network.
  • MST ties: different minimum spanning trees can lead to different odd sets and final tours.
  • Matching solver: use a trusted minimum-weight perfect-matching implementation.
  • Euler traversal: preserve parallel edges in the augmented multigraph.
  • Shortcut policy: record first visits carefully so every required vertex appears exactly once in the final metric tour.
  • Numeric policy: floating-point distances can make equality, tie-breaking and reproducibility subtle.
  • Post-improvement: if local search is added, measure improvement separately from the base approximation algorithm.

Testing ladder

  • three and four vertices where the optimum can be enumerated exactly;
  • points on a line or circle with obvious geometry;
  • instances with many equal edge weights to test tie reproducibility;
  • small Euclidean random instances compared against exhaustive TSP enumeration;
  • incomplete connected graphs passed through metric closure;
  • non-metric examples that deliberately demonstrate why shortcutting can break the guarantee;
  • larger random metrics where the returned tour is checked for uniqueness of visits and cost consistency;
  • cross-checks against NetworkX or another trusted graph library.

Common misconceptions

  • “3/2 means the answer is usually 50% too long.” It is a worst-case upper bound, not an expected error.
  • “The MST plus doubled edges is Christofides.” Doubling the MST gives the simpler 2-approximation; Christofides uses minimum matching on the odd vertices.
  • “Shortcutting always helps.” The non-increase guarantee depends on triangle inequality.
  • “The perfect matching is on all vertices.” It is only on the odd-degree vertices of the MST.
  • “Christofides solves vehicle routing.” Capacities, time windows and multiple vehicles define different problems.

A learning route from beginner to professional

  • Beginner: draw small metric TSP instances and compare greedy tours with the optimum.
  • Intermediate: implement MST, odd-degree detection, perfect matching, Euler traversal and shortcutting as separate modules.
  • Advanced: prove both cost bounds and reconstruct the full 3/2 argument without notes.
  • Algorithm engineer: validate metrics, preserve multigraph semantics, benchmark matching cost and cross-check small cases exhaustively.
  • Professional: decide whether the instance truly fits metric symmetric TSP, compare guaranteed and heuristic methods, and integrate the approximation into a broader optimisation workflow when appropriate.

For teaching, make each subgoal visible. Ask learners to predict which vertices will be odd, run the MST, investigate why the odd count must be even, modify one edge weight, recompute the matching, then explain exactly where triangle inequality enters the proof. The strongest learning task is to give a partially completed Christofides pipeline and ask the learner to diagnose which invariant has been broken.

Authoritative sources and further reading

Closing idea. Christofides’ algorithm teaches that approximation is not surrendering correctness. It is changing the promise: instead of claiming “I found the unknowable optimum,” the algorithm proves “whatever the optimum is, my answer cannot be more than this far away.”