Hamiltonian Path Checker

Check whether a graph contains a Hamiltonian path or Hamiltonian cycle. Runs backtracking with Warnsdorff pruning, verifies connectivity and degree prerequisites, tests Dirac and Ore sufficient conditions, and shows the witness path on an animated SVG visualization.

Embed Hamiltonian Path Checker Widget

About Hamiltonian Path Checker

The Hamiltonian Path Checker decides whether a graph contains a Hamiltonian path — a sequence that visits every vertex exactly once — or a Hamiltonian cycle, which additionally returns to the starting vertex. It combines fast structural pre-checks (connectivity, degree prerequisites, Dirac's theorem, Ore's theorem) with a backtracking search tuned by Warnsdorff's heuristic, and visualizes the witness path with a step-by-step animation.

What Is a Hamiltonian Path?

Given a graph G = (V, E) with n vertices, a Hamiltonian path is an ordered sequence v₁, v₂, …, v_n of all vertices such that each consecutive pair (v_i, v_i+1) is an edge of G, and every vertex appears exactly once. If additionally (v_n, v₁) is an edge, the sequence is a Hamiltonian cycle.

Hamiltonian path: v1 — v2 — v3 — … — vn (all distinct, each consecutive pair is an edge) Hamiltonian cycle: v1 — v2 — v3 — … — vn — v1 (closes back to the start)

The problem is named after William Rowan Hamilton, who in 1857 invented the Icosian game — a puzzle asking the solver to find a cycle visiting every vertex of a regular dodecahedron exactly once.

Why It Is Hard: NP-Completeness

Both the Hamiltonian path decision problem and the Hamiltonian cycle decision problem are NP-complete (Karp, 1972). Unless P = NP, no polynomial-time algorithm exists that solves every instance. In the worst case, backtracking explores a search tree of size up to (n−1)! for a cycle. This is why the calculator caps input at 20 vertices — a small polynomial increase in n produces an explosive increase in run time.

In practice, the Warnsdorff heuristic (originally devised by Heinrich Warnsdorff in 1823 for the knight's tour) makes the search dramatically faster on structured graphs: at each step, the algorithm extends the current path to the unvisited neighbor with the smallest number of remaining unvisited neighbors. This greedy rule keeps the search from painting itself into a corner and often finds a Hamiltonian tour with zero backtracking on well-behaved graphs.

Necessary Conditions — Fast Rejection

Before running an expensive search, the calculator rejects graphs that cannot possibly contain a Hamiltonian path:

Connectivity. A Hamiltonian path must visit every vertex, so the graph must have exactly one connected component. For directed graphs, weak connectivity (ignoring arrow directions) is required.
Degree (undirected). At most two vertices may have degree 1 — those are the only candidates for the path's endpoints. For a Hamiltonian cycle, every vertex must have degree at least 2.
Degree (directed). For a Hamiltonian path, at most one vertex may have in-degree 0 (the start) and at most one may have out-degree 0 (the end). For a Hamiltonian cycle, every vertex must have both in-degree ≥ 1 and out-degree ≥ 1.

These rules reject many hopeless inputs in linear time, avoiding wasted backtracking effort.

Sufficient Conditions — Classical Theorems

Several classical theorems give sufficient (but not necessary) conditions guaranteeing a Hamiltonian cycle in undirected simple graphs. If any of these apply, the calculator marks the result "GUARANTEES" without even running the search — though it still exhibits a witness cycle.

Dirac's Theorem (1952)

If G is a simple undirected graph on n ≥ 3 vertices and every vertex has degree at least n / 2, then G has a Hamiltonian cycle.

δ(G) ≥ n / 2 ⟹ G is Hamiltonian

Ore's Theorem (1960)

If for every pair of non-adjacent vertices u and v we have deg(u) + deg(v) ≥ n, then G has a Hamiltonian cycle. Ore's condition is strictly weaker than Dirac's, so Ore implies Dirac.

∀ non-adjacent u, v: deg(u) + deg(v) ≥ n ⟹ G is Hamiltonian

Failure of Dirac's or Ore's condition does not mean the graph lacks a Hamiltonian cycle — many graphs satisfy neither but still contain one (e.g., a simple n-cycle has minimum degree 2, far below n/2 for large n).

The Search Algorithm Inside

When the pre-checks do not settle the question, the calculator runs a backtracking search on the graph's adjacency representation. Key tactics:

Bitmask visited-set. The visited vertices are stored as a bitmask (fast O(1) membership test for up to 20 vertices).
Warnsdorff heuristic. At each extension, neighbors are tried in order of their remaining unvisited-degree (smallest first), mimicking a "low-branching" order.
Root selection. For Hamiltonian cycle, only one starting vertex is needed (cycles are rotation-invariant). For Hamiltonian path, starts are tried in ascending order of out-degree — the rarest positions first.
Step budget. A hard cap prevents pathological instances from running indefinitely; the UI reports the verdict as "timed out" if the budget is exhausted.

Hamiltonian vs Eulerian

It is easy to confuse Hamiltonian and Eulerian problems — they sound similar but are fundamentally different:

Property	Hamiltonian path / cycle	Eulerian trail / circuit
Visits each…	Vertex exactly once	Edge exactly once
Complexity	NP-complete	Polynomial (O(n+m))
Condition	No simple characterization	Connected + all degrees even (for circuit); at most 2 odd for trail
Named after	W. R. Hamilton (1857)	L. Euler (1736, Königsberg bridges)
Classic example	Traveling Salesman, Icosian game	Route inspection, postman problem

Supported Input Formats

Edge list

One edge per line, or comma-separated. Supported separators: A-B, A B, A,B, A--B, A->B, A<-B. Use -> to force a directed interpretation.

A-B, B-C, C-D, D-A, A-C (undirected graph with 5 edges) A->B, B->C, C->D, D->A (directed 4-cycle)

Adjacency matrix

Square matrix of 0/1 values, one row per line, space- or comma-separated. Supply optional labels in the Matrix labels field; otherwise A, B, C… are used automatically.

0 1 1 0 1 0 1 1 1 1 0 1 0 1 1 0

How to Use This Checker

Pick an input format — Edge list for small hand-written graphs, Adjacency matrix for pastes from code or textbooks.
Paste your graph in the text area. For matrix input, optionally provide vertex labels.
Choose what to check: Path only, Cycle only, or Both in one run.
Select graph type — Auto-detect infers directedness from arrow style (->) or matrix symmetry.
Click Check Hamiltonian. The result page shows a verdict headline, the necessary-condition pre-check, Dirac / Ore sufficient-condition tests, the witness path (if one exists), and an interactive visualization.
Replay the witness using the Play / Step controls. Watch the path light up edge by edge on the graph.

Worked Example — The Petersen Graph

The famous Petersen graph (10 vertices, 15 edges, 3-regular) is a textbook example of a graph with a Hamiltonian path but no Hamiltonian cycle. Paste this into the edge-list field and click Check:

1-2, 2-3, 3-4, 4-5, 5-1, 6-8, 8-10, 10-7, 7-9, 9-6, 1-6, 2-7, 3-8, 4-9, 5-10

The checker confirms: Hamiltonian path found (e.g., 1 — 2 — 7 — 10 — 5 — 4 — 9 — 6 — 8 — 3), but exhaustive search finds no way to close the loop back — a result first proved in the 1890s.

Common Applications

Routing and the Traveling Salesman Problem — every TSP tour is a Hamiltonian cycle in the complete weighted graph.
Genome assembly — reconstructing a DNA sequence from overlapping reads can be modeled as a Hamiltonian path in an overlap graph.
Circuit layout — ordering pins on a PCB for minimum-length wiring.
Game AI and puzzle solving — knight's tours on a chessboard, Icosian game.
Scheduling — sequencing tasks so that each one transitions feasibly to the next.
Combinatorics teaching — illustrating NP-completeness with tiny hand-solvable examples.

Frequently Asked Questions

What is a Hamiltonian path?

A Hamiltonian path is a walk through a graph that visits every vertex exactly once. It is named after William Rowan Hamilton, who studied the problem on the dodecahedron graph in 1857. Deciding whether such a path exists is an NP-complete problem, so no known algorithm solves it in polynomial time for all graphs.

How is a Hamiltonian cycle different from a Hamiltonian path?

A Hamiltonian cycle is a Hamiltonian path that returns to its starting vertex, forming a closed loop that visits every vertex exactly once. Every Hamiltonian cycle contains a Hamiltonian path (just drop the closing edge), but the reverse is not true: many graphs have a Hamiltonian path but no Hamiltonian cycle.

What does Dirac's theorem say?

Dirac's theorem (1952) states that any simple undirected graph on n ≥ 3 vertices in which every vertex has degree at least n/2 contains a Hamiltonian cycle. It is a sufficient but not necessary condition: many graphs that fail the Dirac threshold still have Hamiltonian cycles.

What does Ore's theorem say?

Ore's theorem (1960) states that if, for every pair of non-adjacent vertices u and v in a simple graph on n ≥ 3 vertices, the sum of their degrees is at least n, then the graph has a Hamiltonian cycle. Ore's condition is weaker than Dirac's, so Ore's theorem applies whenever Dirac's theorem does.

Why is the search limited to 20 vertices?

Hamiltonian path and cycle decision problems are NP-complete. Worst-case running time scales exponentially with the number of vertices. With pruning and the Warnsdorff heuristic the calculator handles many small graphs up to 20 vertices quickly, but harder instances may time out. Beyond 20 vertices you should use specialized solvers such as Concorde or integer-programming formulations.

What is Warnsdorff's heuristic?

Warnsdorff's rule, proposed in 1823 for the knight's tour problem, says that at each step you should visit the next-vertex that has the fewest remaining unvisited neighbors. This greedy-looking rule dramatically prunes the backtracking tree in practice and often finds Hamiltonian paths without backtracking at all on regular graphs.

Does this tool find all Hamiltonian paths?

No — it finds a single witness path or cycle when one exists. Counting the total number of Hamiltonian paths is itself a #P-complete problem and far harder than the decision problem. For enumeration, specialized tools or integer-programming solvers are more appropriate.

Related MiniWebtools:

Adjacency Matrix CalculatorNew

Dijkstra's Shortest Path CalculatorNew

Graph Coloring CalculatorNew

Topological Sort CalculatorNew

Traveling Salesman Solver (TSP)New

Hamiltonian Path Checker

About Hamiltonian Path Checker

What Is a Hamiltonian Path?

Why It Is Hard: NP-Completeness

Necessary Conditions — Fast Rejection

Sufficient Conditions — Classical Theorems

Dirac's Theorem (1952)

Ore's Theorem (1960)

The Search Algorithm Inside

Hamiltonian vs Eulerian

Supported Input Formats

Edge list

Adjacency matrix

How to Use This Checker

Worked Example — The Petersen Graph

Common Applications

Frequently Asked Questions

What is a Hamiltonian path?

How is a Hamiltonian cycle different from a Hamiltonian path?

What does Dirac's theorem say?

What does Ore's theorem say?

Why is the search limited to 20 vertices?

What is Warnsdorff's heuristic?

Does this tool find all Hamiltonian paths?

Further Reading

Related MiniWebtools:

Advanced Math Operations:

Top & Updated: