Hamiltonian Cycles

Graph Theory · Axiom Academy

Exploring cycles that visit every vertex exactly once 1. Definition of a Hamiltonian Cycle A Hamiltonian cycle (also called a Hamiltonian circuit ) in a graph G is a cycle that visits every vertex of G exactly once and returns to the starting vertex. The animation below demonstrates a Hamiltonian cycle in a simple graph. Watch as we traverse the cycle, visiting each vertex exactly once before returning to the start. 2. Hamiltonian Paths vs Cycles A Hamiltonian path is similar to a Hamiltonian cycle, but it does not need to return to the starting vertex. Every Hamiltonian cycle contains a Hamiltonian path, but not every Hamiltonian path can be extended to a Hamiltonian cycle. The animation shows the difference between a Hamiltonian path (green) and a Hamiltonian cycle (blue). Notice how the path visits all vertices but doesn't close the loop, while the cycle returns to the starting point. 3. Complete Graphs are Hamiltonian A powerful result: Every complete graph K n with n ≥ 3 vertices is Hamiltonian . This is because in a complete graph, every vertex is connected to every other vertex, making it always possible to construct a cycle visiting each vertex exactly once. Watch the animation showing a Hamiltonian cycle in K 5 , the complete graph with 5 vertices. 4. The Petersen Graph: A Famous Non-Hamiltonian Graph

This is the written version of the interactive lesson above. See the full Graph Theory course.