Hamiltonian Path Checker
Decide whether an undirected graph has a path visiting every node exactly once, with an exhaustive backtracking search that prints the path or proves there is none.
Hamiltonian Path Checker
Decide whether an undirected graph has a path visiting every node exactly once, with an exhaustive backtracking search that prints the path or proves there is none.
How this page computes
The adjacency map is built from the edge list with neighbours in first-appearance order, so the search is deterministic. Each start node is tried in turn, and a recursive walk marks, tries and unmarks.
The walk stops at a full path or at the step budget. A completed search with no path prints the node and edge counts beside the conclusion, so the claim rests on the counts it examined.
The calculation runs entirely in this browser tab; nothing is uploaded.
The page looks for a path that visits every node exactly once — no return to the start, unlike a tour. On the four-node square A-B-C-D-A it finds A, B, C, D, and it found it by trying every alternative rather than by a rule of thumb.
When no such path exists the page says so after exhausting the search, and when the graph is too dense to finish within its step budget it says that instead. "None exists" and "not found in time" are different answers, and the page never merges them.
How to use Hamiltonian Path Checker
Type the edges one per line and press Run. The page accepts an undirected list, so A B and B A mean the same edge.
The output is the path as a node sequence, or a refusal naming the node count and the edge count with the conclusion that none exists. The step count shows how much of the search space was walked.
Backtracking, and the budget it must respect
Start at a node, mark it used, and try each unvisited neighbour in turn. If a full path is reached, stop and print it. If a branch dead-ends, unmark the last node and try the next neighbour — that is the whole algorithm, and it is exhaustive, so a completed search is a proof.
Exhaustive search is factorial in the worst case, so the page counts its steps and stops at four million. Past that it refuses with the reason, because a graph dense enough to exhaust the budget would otherwise freeze the tab and still not answer.
What to Expect
Best for
- Deciding whether a small graph has a Hamiltonian path
- Checking a hand-drawn puzzle answer
- Seeing an exhaustive search and its cost
Not ideal for
- Graphs above fourteen nodes, which need a different method
- A closed tour back to the start, which is the TSP page
- Dense graphs that exhaust the step budget
What this tool keeps
- Every node and every edge
What may need cleanup
- Nothing when a path is found; nothing when none exists either
Common errors
- A step budget is reported rather than a false "none exists"
- More than fourteen nodes is refused with the ceiling named
Example use cases
- Check that a four-node cycle has a Hamiltonian path
- Show that a star graph of five nodes does not
- See how many branches an exhaustive search tries
Sample input
edges A-B, B-C, C-D, D-A
Sample output
Hamiltonian path A -> B -> C -> D
Who this is for
- Students meeting NP-complete problems
- Puzzle solvers checking a route
Frequently asked questions
What is the difference between a Hamiltonian path and a tour?
A tour returns to the start and a path does not. This page answers the open path; the traveling salesman page answers the closed tour, and a path exists whenever a tour does.
Why does the answer take longer on some graphs?
Because the search is exhaustive: a graph with many edges offers many orderings to try. The page counts its steps and stops at four million rather than let the tab hang.
Can a node have degree zero?
Yes, but then no Hamiltonian path exists unless it is the only node, because the isolated node can never be reached. The search discovers that by failing to reach it from anywhere.
Build custom tools for your store
Join the SDK program to create useful ecommerce utilities for your store.