Hamiltonian Paths and Cycles

Math for CS · Axiom Academy

Visiting every vertex exactly once Named after the Irish mathematician William Rowan Hamilton, who in 1857 created the "Icosian game" — a puzzle asking players to find a Hamiltonian cycle on the edges of a dodecahedron. These two problems sound similar but are fundamentally different in computational difficulty. Visit every edge exactly once. Existence: simple degree check. Visit every vertex exactly once. Existence: no known simple condition. Finding one: no known polynomial algorithm. Complexity: NP-complete (hard). While there is no simple necessary and sufficient condition (unlike Euler paths), several theorems give sufficient conditions guaranteeing a Hamiltonian cycle exists. Ore's theorem is strictly more general than Dirac's — every graph satisfying Dirac's condition also satisfies Ore's, but not vice versa. The Traveling Salesman Problem (TSP) The most famous problem connected to Hamiltonian cycles is the Traveling Salesman Problem : given a weighted complete graph, find the minimum-weight Hamiltonian cycle. TSP is NP-hard, meaning no known polynomial algorithm solves it exactly. The brute-force approach tries all (n-1)! possible tours — for 20 cities, that is roughly tours. Exact algorithms: Dynamic programming (Held-Karp) runs in — feasible for . Approximation: For metric TSP (triangle inequality holds), the Christofides algorithm guarantees a tour within 1.5x of optimal.

This is the written version of the interactive lesson above. See the full Math for CS course.