Lesson 181
Hamiltonian Paths
Graph Theory · NP-Complete · TSP
1:00How to find a route through a graph that visits every vertex exactly once — and why it is one of computer science's hardest problems.
By the end, you can
- Define a Hamiltonian path and a Hamiltonian cycle, and state how they differ.
- Distinguish a Hamiltonian path (every vertex once) from an Eulerian path (every edge once).
- Apply the fast Eulerian existence rule and explain why no equivalent rule exists for Hamiltonian paths.
- Explain what NP-complete means for the Hamiltonian path problem — hard to find, trivial to verify.
- Trace the backtracking algorithm on a small graph, including correctly identifying and undoing dead ends.
- Compare O(n!) brute force with Held–Karp O(n²·2ⁿ) and explain why Held–Karp is preferred.
- State Dirac's and Ore's theorems and explain that they are sufficient but not necessary conditions.
- Describe the Traveling Salesman Problem as the weighted optimization extension of Hamiltonian cycles.
- Give real-world examples of Hamiltonian paths in routing, genomics, and scheduling.
Up next in Algorithms & Graph Algorithms
