Hamiltonian Paths and Cycles: Definition and Examples
What you'll learn: You'll discover what it means for a path to visit every vertex in a graph exactly once, and when such a path forms a cycle.
The Core Idea
While Eulerian paths focus on traversing every edge exactly once, Hamiltonian paths focus on visiting every vertex exactly once.
A Hamiltonian path in a graph is a path that visits each vertex in the graph exactly one time. Think of it like a traveling salesperson who must visit every city on their map exactly once, but doesn't need to return home.
A Hamiltonian cycle (or Hamiltonian circuit) is a Hamiltonian path that returns to its starting vertex, forming a closed loop. This is like the salesperson's route when they must also return to their home city after visiting all others exactly once.
Key Differences from Eulerian Concepts
- Eulerian: Focus on edges (traverse every edge once)
- Hamiltonian: Focus on vertices (visit every vertex once)
Notably, determining whether a Hamiltonian path or cycle exists is much harder than for Eulerian paths—there's no simple degree-checking rule like Euler's Theorem.
Simple Example
Consider a graph with vertices {A, B, C, D} arranged in a square with edges A–B, B–C, C–D, D–A, and a diagonal A–C.
- Hamiltonian path: A → B → C → D (visits all 4 vertices once)
- Hamiltonian cycle: A → B → C → D → A (visits all 4 vertices and returns to start)
Not every graph has a Hamiltonian path or cycle. Finding them often requires systematic exploration or clever reasoning about the graph's structure.
Key Takeaway: A Hamiltonian path visits every vertex exactly once; a Hamiltonian cycle does the same but returns to the starting vertex, forming a closed tour through all vertices.