Hamiltonian Paths and Cycles in Graph Theory Explained

A Hamiltonian path is a path that visits every vertex of a graph exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex — a single grand tour touching each vertex once and only once. They are named after William Rowan Hamilton, who in 1857 marketed the "icosian game": find such a tour on a dodecahedron.

Hamiltonian cycles matter because they model the perfect route: a salesperson visiting every city once or a delivery round with no repeats. Unlike Eulerian trails, which are easy to test for, Hamiltonian problems are famously hard — and that hardness itself matters in computer science.

Key Concepts

• Hamiltonian path: visits each vertex exactly once; in a graph with n vertices it has length n − 1.
• Hamiltonian cycle: a closed Hamiltonian path of length n, returning to the start.
• Dirac's theorem: if n ≥ 3 and every vertex has degree at least n/2, a Hamiltonian cycle exists. Sufficient but not necessary.
• Ore's theorem: if deg(u) + deg(v) ≥ n for every non-adjacent pair u, v, a Hamiltonian cycle exists. Also sufficient, not necessary.
• NP-complete: no known fast test decides whether a Hamiltonian cycle exists; known methods can take exponential time. Euler had a one-line test; Hamilton has none.

How It Works

Finding a Hamiltonian cycle is a search. Start at a vertex, move to an unvisited neighbour, and keep going without revisiting vertices. If you get stuck early, backtrack to the last choice point and try a different neighbour. This backtracking always finds a cycle if one exists, but on large graphs it can explore an enormous number of dead ends — that is why the problem is NP-complete. Dirac's and Ore's theorems give shortcuts: if degrees are high enough, you can declare success without searching. But many Hamiltonian graphs have low-degree vertices, so the theorems stay silent and only the search can answer.

Worked Example

Graph with 5 vertices {A, B, C, D, E} and edges: A–B, B–C, C–D, D–E, E–A, A–C, B–D. Search by backtracking: start at A, go to B, then C, then D (all unvisited). From D, the unvisited neighbour is E — go to E. From E, the only unvisited option is the start A. The cycle A–B–C–D–E–A visits all 5 vertices exactly once — a Hamiltonian cycle of length 5. Check Dirac: degrees are 3, 3, 3, 3, 2, and n/2 = 2.5 — every degree is at least 2.5, so Dirac's theorem guarantees a cycle, matching the search result.

Common Misconceptions

• Hamiltonian and Eulerian are different problems. Euler covers every edge once (vertices may repeat); Hamilton visits every vertex once (edges may be skipped). A graph can have one, both, or neither.
• Failing Dirac's or Ore's test proves nothing. These theorems are one-way: passing them guarantees a Hamiltonian cycle, but failing them does not rule one out. The worked example above would still have a cycle even with a lower-degree vertex added.
• High connectivity does not guarantee a Hamiltonian cycle. The Petersen graph is highly symmetric and connected, yet famously has no Hamiltonian cycle.

Real-World Applications

• Travelling salesperson problem: the shortest Hamiltonian cycle through a set of cities is one of the most studied optimisation problems in logistics.
• Genome assembly: ordering DNA fragments so each is visited once is a Hamiltonian path problem.

A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle closes the loop. There is no simple counting test like Euler's — only sufficient conditions such as Dirac's and Ore's, plus backtracking search.