A Hamiltonian path visits every vertex of a graph exactly once. A Hamiltonian cycle does the same but finishes at the starting vertex, creating a closed route.
This is HL-only content in AHL 3.16: Tree and cycle algorithms, Chinese postman, travelling salesman.
How They Work
Suppose a graph has vertices (A,B,C,D). The route
is Hamiltonian if each of the graph's four vertices is visited exactly once. It is a path rather than a cycle because it does not return to .
If an edge connects to , then
is a Hamiltonian cycle. The starting vertex appears again only to close the cycle; no other vertex is repeated.
A graph may have several Hamiltonian paths or cycles, or none at all. For a Hamiltonian cycle to exist, every vertex must have degree at least , but this condition alone does not guarantee one.
Hamiltonian Versus Eulerian Routes
| Route type | Requirement |
|---|---|
| Hamiltonian path | Visits every vertex exactly once |
| Hamiltonian cycle | Visits every vertex exactly once and returns to the start |
| Eulerian trail | Uses every edge exactly once |
| Eulerian circuit | Uses every edge exactly once and returns to the start |
The common misconception is that Hamiltonian routes must use every edge. They do not: Hamiltonian problems focus on vertices, while Eulerian problems focus on edges.
Hamiltonian cycles are central to the travelling salesman problem, where the objective is to find the least-weight Hamiltonian cycle in a weighted complete graph. In IB Mathematics: Applications and Interpretation HL, you may use the nearest-neighbour algorithm to obtain an upper bound or the deleted-vertex algorithm to obtain a lower bound.
Exam Technique
When asked to identify a Hamiltonian path or cycle, write the complete vertex sequence and check every vertex exactly once. For a cycle, also verify that the final vertex is adjacent to the starting vertex; do not confuse this with an Eulerian route.
