Hamiltonian Path Checker

What Is a Hamiltonian Path?

A Hamiltonian path is a path through a graph that visits every vertex exactly once. The concept is named after the Irish mathematician Sir William Rowan Hamilton, who in 1857 devised the Icosian game — a puzzle asking players to find a cycle that traverses all 20 vertices of a dodecahedron graph. Unlike an Eulerian path, which traverses every edge exactly once, a Hamiltonian path is concerned exclusively with vertices: each must be visited once and only once.

Hamiltonian Path vs. Eulerian Path

These two classical problems look similar but differ fundamentally in complexity. An Eulerian path (visiting every edge once) has a clean, efficient solution: Hierholzer's algorithm runs in O(E) time, and a simple rule — at most two vertices of odd degree — decides whether one exists. By contrast, deciding whether a Hamiltonian path exists is NP-complete. This means no polynomial-time algorithm is known, and the problem is believed to require exponential time in the worst case for general graphs.

Hamiltonian Cycle

A Hamiltonian cycle (also called a Hamiltonian circuit) is a Hamiltonian path that returns to its starting vertex, forming a closed loop. Every graph that has a Hamiltonian cycle also has a Hamiltonian path (just delete one edge), but the reverse is not true. For example, a simple path graph 1–2–3–4 has a Hamiltonian path but no Hamiltonian cycle, since vertex 4 cannot return to vertex 1 without revisiting 2 or 3.

Dirac's Theorem (1952)

Dirac's theorem, proved by Gabriel Andrew Dirac in 1952, gives the most widely cited sufficient condition for the existence of a Hamiltonian cycle: if a simple undirected graph on n ≥ 3 vertices has every vertex with degree at least n/2, then the graph contains a Hamiltonian cycle. This condition is strong but not necessary — many graphs with lower-degree vertices still have Hamiltonian cycles. This tool checks Dirac's condition as a quick pre-filter before running the full backtracking search.

Ore's Theorem (1960)

Ore's theorem, proved by Oystein Ore in 1960, is a generalization of Dirac's result. It states: if for every pair of non-adjacent vertices u and v in a graph on n ≥ 3 vertices, the sum of their degrees satisfies deg(u) + deg(v) ≥ n, then a Hamiltonian cycle exists. Ore's condition is weaker than Dirac's (every graph satisfying Dirac's also satisfies Ore's), so it applies to more graphs. Both are sufficient, not necessary, conditions.

Backtracking Algorithm

This checker uses a backtracking depth-first search to find Hamiltonian paths. Starting from a chosen vertex, the algorithm tries to extend the current path by appending an unvisited adjacent vertex. If no valid extension exists and the path does not yet span all vertices, it backtracks — removing the last vertex and trying the next candidate. When the path reaches all n vertices, a Hamiltonian path is recorded. If the last vertex is also adjacent to the start, a Hamiltonian cycle is found. To protect browser performance, the search stops after 100,000 recursive calls.

Applications of Hamiltonian Paths

• Travelling Salesman Problem (TSP): Finding the shortest Hamiltonian cycle in a weighted graph. The unweighted version reduces to the Hamiltonian cycle problem solved here.
• DNA Fragment Assembly: Sequencing short DNA reads can be modeled as finding a Hamiltonian path through an overlap graph.
• Scheduling and Sequencing: Job scheduling where each job must be done once and job-to-job transitions are constrained maps to Hamiltonian path existence.
• Knight's Tour: The chess knight's tour problem — visiting every square of a chessboard exactly once — is a Hamiltonian path problem on the knight-move graph.
• Gray Codes: A standard binary Gray code is a Hamiltonian cycle on the n-dimensional hypercube graph.
• Network Routing: Certain routing protocols require visiting every node once; the existence question is exactly the Hamiltonian path problem.

NP-Completeness

Richard Karp's 1972 landmark paper "Reducibility Among Combinatorial Problems" listed the Hamiltonian cycle problem as one of 21 NP-complete problems. This means: (1) any proposed solution can be verified in polynomial time, but (2) no polynomial-time finding algorithm is known. In practice, for graphs with up to about 15 vertices backtracking is feasible. For larger instances, heuristics, dynamic programming (Held-Karp, O(2^n · n^2)), and approximation algorithms are used.

Reference: Hamiltonian Properties of Classic Graphs