Hamiltonian Path Calculator
Check whether a Hamiltonian path exists in a small graph via backtracking search.
About Hamiltonian Path Calculator
A Hamiltonian path visits every vertex in a graph exactly once. A Hamiltonian cycle is a Hamiltonian path that returns to the starting vertex. This calculator uses backtracking search, which is exact but exponential in time complexity.
Formula
Backtracking: try extending the current path to each unvisited neighbor; backtrack if stuck
- n
- Number of vertices
Worked example
With the default values below, Hamiltonian Path Calculator returns Hamiltonian Path Exists? of Yes. Change any input above and every figure here is recalculated in your browser.
Inputs used
- Vertices (comma separated)
- A, B, C, D, E
- Edges (semicolon separated pairs)
- A-B; A-C; B-C; B-D; C-D; D-E; C-E
Results
- Hamiltonian Path Exists?
- Yes
- Path Found
- A → B → C → D → E
- Hamiltonian Cycle Exists?
- No
Step by step
- 1Values used
- 2Formula applied
- 3Hamiltonian Path Exists?= Yes
- 4Path Found= A → B → C → D → E
- 5Hamiltonian Cycle Exists?= No
Assumptions and limits
- The result is derived only from the 2 inputs listed above. Anything not among them is not part of the calculation.
- In particular, this calculator does not take inflation, tax, fees or charges or compounding frequency into account.
How these calculators are built and tested is described on the Methodology page. If a figure looks wrong, please report it.
Frequently Asked Questions
Why is finding a Hamiltonian path hard?
It is NP-complete — no known polynomial-time algorithm exists. For small graphs backtracking is feasible, but it becomes impractical for large graphs.
How does this differ from an Euler path?
A Hamiltonian path visits every vertex exactly once. An Euler path traverses every edge exactly once. They are fundamentally different problems.