Hamiltonian Paths

Graph Theory · Axiom Academy

Exploring paths that visit every vertex exactly once 1. Definition: What is a Hamiltonian Path? A Hamiltonian path in a graph G is a path that visits every vertex exactly once. If such a path forms a cycle (returns to the starting vertex), it's called a Hamiltonian cycle . Each vertex appears exactly once Consecutive vertices are adjacent in the graph The path contains all n vertices of G Watch the animation to see a Hamiltonian path being traced through a graph: 2. The Missing Theorem (Unlike Eulerian Paths!) Eulerian paths have a beautiful, simple characterization: a connected graph has an Eulerian path if and only if it has exactly 0 or 2 vertices of odd degree. Compare these two graphs below. One has a Hamiltonian path, the other does not. Can you tell which is which just by looking at their properties? 3. Computational Complexity: NP-Complete The Hamiltonian path problem is one of the famous NP-complete problems. This means: Easy to verify: Given a path, we can quickly check if it's Hamiltonian Hard to find: No known efficient algorithm exists to determine if a Hamiltonian path exists Worst case: May need to check exponentially many possible paths The animation shows how the search space grows exponentially with graph size: 4. Sufficient Conditions (Dirac's Theorem) While we lack a complete characterization, we do have sufficient conditions - rules that guarantee a Hamiltonian cycle exists (though they're not necessary).

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