Hamiltonian Path Checker screenshot

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.

Privacy First
0 Runs
Updated 2026-11-22
Runs in your browser
No sign-up, no upload
Reports its own budget

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.

Developer program

Build custom tools for your store

Join the SDK program to create useful ecommerce utilities for your store.