Hamiltonian Cycles and Paths

While Eulerian circuits visit every edge exactly once, Hamiltonian cycles visit every vertex exactly once. Despite this similar-sounding definition, the Hamiltonian problem is dramatically harder—it's NP-complete, with no efficient algorithm known.

DefinitionHamiltonian Cycle and Path

A Hamiltonian cycle is a cycle that visits every vertex of a graph exactly once (except the start/end vertex which appears twice). A Hamiltonian path visits every vertex exactly once with no return to the start.

A graph is Hamiltonian if it contains a Hamiltonian cycle, and traceable if it contains a Hamiltonian path.

Unlike Eulerian graphs, no simple characterization exists for Hamiltonian graphs. The decision problem "does graph $G$ have a Hamiltonian cycle?" is NP-complete, making it computationally intractable for large graphs.

TheoremDirac's Theorem

If $G$ is a connected graph with $n \geq 3$ vertices and every vertex has degree at least $n/2$ , then $G$ is Hamiltonian.

This sufficient condition guarantees a Hamiltonian cycle through a minimum degree requirement, though the condition is not necessary.

TheoremOre's Theorem

If $G$ has $n \geq 3$ vertices and for every pair of non-adjacent vertices $u,v$ , we have $\deg(u) + \deg(v) \geq n$ , then $G$ is Hamiltonian.

Ore's theorem generalizes Dirac's: if $\deg(u) \geq n/2$ for all $u$ , then $\deg(u) + \deg(v) \geq n$ for any pair.

ExamplePetersen Graph

The Petersen graph is a famous counterexample: it has 10 vertices, each of degree 3, but is non-Hamiltonian. It satisfies many nice properties (vertex-transitive, 3-connected) yet has no Hamiltonian cycle. This shows that high connectivity doesn't guarantee Hamiltonicity.

However, the Petersen graph does have many Hamiltonian paths, demonstrating that non-Hamiltonian graphs can still be traceable.

DefinitionTraveling Salesman Problem (TSP)

Given a weighted complete graph $K_n$ , find a Hamiltonian cycle of minimum total weight. This is the Traveling Salesman Problem, one of the most famous NP-hard optimization problems.

Approximation algorithms exist: the Christofides algorithm guarantees a solution within 1.5× optimal for metric TSP (where edge weights satisfy the triangle inequality).

Remark

Knight's Tour problem asks whether a knight can visit every square of a chessboard exactly once, moving according to chess rules. This is a Hamiltonian path problem on the knight's graph. An $8 \times 8$ board admits many knight's tours, but determining their existence for arbitrary board sizes remains an interesting combinatorial problem.

DefinitionComputational Complexity

Eulerian circuit: Polynomial time $O(m)$ (Hierholzer's algorithm)
Hamiltonian cycle: NP-complete (no known polynomial algorithm)

This stark contrast illustrates how superficially similar problems can have vastly different computational complexity. The Hamiltonian cycle problem remains one of Karp's original 21 NP-complete problems.

The difficulty of the Hamiltonian problem has driven development of approximation algorithms, heuristics, and complexity theory, while also finding applications in logistics, DNA sequencing, and circuit board drilling optimization.