A Hamiltonian path is a route through a network (called a graph in mathematics) that visits every point exactly once. If you imagine a map of cities connected by roads, a Hamiltonian path would be a trip that passes through every city on the map without revisiting any of them. It’s one of the most important concepts in graph theory, and it turns out to be surprisingly difficult to find in practice.
How a Hamiltonian Path Works
In graph theory, a “graph” is simply a collection of points (called vertices) connected by lines (called edges). A Hamiltonian path starts at one vertex, travels along edges, and ends at another vertex, hitting every vertex in the graph exactly once along the way. The key rule: no vertex gets a second visit.
This is different from a Hamiltonian cycle, which is the closely related version where you must also return to your starting point. A cycle forms a complete loop through every vertex. A path just needs to reach them all, and it can end wherever it ends. Every Hamiltonian cycle contains a Hamiltonian path (just remove the final return trip), but a graph can have a Hamiltonian path without having a Hamiltonian cycle.
Not every graph has a Hamiltonian path at all. Some networks are simply arranged in a way that makes it impossible to visit every point without backtracking. A graph that does contain a Hamiltonian path is called “traceable.”
Hamiltonian Paths vs. Eulerian Paths
These two concepts get mixed up constantly, and the distinction is simple. A Hamiltonian path visits every vertex exactly once. An Eulerian path crosses every edge exactly once. One cares about the points, the other cares about the connections between them.
An Eulerian path might visit the same vertex multiple times, as long as it travels each edge only once. A Hamiltonian path might skip some edges entirely, as long as it touches every vertex. In many graphs, one type of path exists but not the other.
Where the Name Comes From
The concept is named after the Irish mathematician William Rowan Hamilton, who invented a puzzle called the Icosian Game in 1857. The game challenged players to find a route along the edges of a dodecahedron (a 12-faced solid) that visited every corner exactly once and returned to the start. Hamilton sold the game to a London dealer in 1859 for 25 pounds, and it was marketed across Europe in several forms. The puzzle was essentially asking players to find a Hamiltonian cycle on a specific graph.
Why Finding One Is So Hard
Determining whether a Hamiltonian path exists in a given graph is classified as NP-complete, a category of problems for which no known algorithm can find a solution efficiently in every case. As the number of vertices grows, the time required to check all possible routes explodes. For a graph with just 20 vertices, there are trillions of possible orderings to consider.
This stands in sharp contrast to Eulerian paths, where a simple rule tells you immediately whether one exists (every vertex needs an even number of connections, with at most two exceptions). No comparable shortcut exists for Hamiltonian paths. You can check specific conditions that guarantee one exists, but there’s no quick test that works on every graph.
One well-known guarantee comes from Dirac’s theorem: if every vertex in a graph with at least three vertices is connected to at least half of the other vertices, the graph is guaranteed to have a Hamiltonian cycle (and therefore a Hamiltonian path). This is a sufficient condition, though. Plenty of graphs that don’t meet Dirac’s threshold still have Hamiltonian paths.
There’s also an interesting result for a structure called a tournament, which is a graph where every pair of points has exactly one directed connection between them (think of a round-robin sports bracket where every team plays every other team once). Rédei’s theorem guarantees that every tournament contains a Hamiltonian path. No exceptions.
Real-World Applications
The Hamiltonian path problem shows up whenever you need to visit a set of locations, tasks, or items exactly once. Delivery route planning, circuit board design, and scheduling problems all involve some version of it. The famous traveling salesman problem, which asks for the shortest possible route visiting a set of cities, is essentially a Hamiltonian path problem with the added constraint of minimizing total distance.
In biology, Hamiltonian paths play a role in DNA sequencing. In 1994, the computer scientist Leonard Adleman demonstrated that DNA molecules could be used to solve a Hamiltonian path problem, encoding a 7-vertex graph using short strands of synthetic DNA. This pioneering experiment launched the field of DNA computing and showed that biological molecules could, in principle, explore vast numbers of possible paths simultaneously. Later researchers extended the approach to graphs with 8 vertices and multiple Hamiltonian paths, testing how well the method scaled.
The core challenge in all these applications is the same: as the problem grows, brute-force searching becomes impractical. Real-world solutions typically rely on approximation algorithms or heuristics that find good-enough answers without guaranteeing the absolute best one.
Simple Examples
Picture five cities arranged in a line, each connected only to its neighbors. A Hamiltonian path is straightforward: just walk from one end to the other. Now rearrange those five cities into a star shape, with one city in the center connected to the other four, but the outer four not connected to each other. A Hamiltonian path still exists (start at an outer city, go to the center, then visit the remaining outer cities), but a Hamiltonian cycle does not, because you can’t get back to the start without revisiting the center.
Now imagine four cities where each one connects to every other one (a complete graph). Here, every possible ordering of the cities is a valid Hamiltonian path. The more connections a graph has, the more likely a Hamiltonian path exists, which is the intuition behind Dirac’s theorem.
For small graphs, you can find Hamiltonian paths by trial and error. For large ones, that approach falls apart quickly, which is precisely what makes this simple-sounding concept one of the deepest unsolved challenges in computer science.