Hamiltonian Path Calculator
Check whether a Hamiltonian path exists in a small graph via backtracking search.
Inputs
Format: X-Y separated by semicolons
Hamiltonian Path Exists?
Yes
Path Found
A → B → C → D → E
Hamiltonian Cycle Exists?
No
Step by step
Values 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
Formula applied
Backtracking: try extending the current path to each unvisited neighbor; backtrack if stuck
Hamiltonian Path Exists?
= Yes
Path Found
= A → B → C → D → E
Hamiltonian Cycle Exists?
= No
How it works
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
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.