Hamiltonian Cycles

A Hamiltonian cycle visits every vertex exactly once and returns to its start. An Eulerian trail uses every edge exactly once; its existence and construction have efficient algorithms under the appropriate connectivity and degree conditions. Deciding whether a general graph has a Hamiltonian cycle is NP-complete.

Worked Example

Consider a simple undirected graph with 5 vertices (labeled 0 to 4) and the following edges:0 1; 1 2; 2 3; 3 4; 0 4; 0 2; 1 3.

We want to enumerate all distinct, undirected Hamiltonian cycles. To do this systematically without double-counting, we can anchor the cycle at vertex 0 and examine permutations of the remaining vertices (1, 2, 3, 4). Since an undirected cycle can be traversed in two directions, we consider only permutations where the first vertex after 0 is less than the last vertex before returning to 0 (the first remaining label is less than the last).

This gives us a maximum of 12 canonical permutations to check. By testing each candidate against our set of edges, we find that exactly two candidate cycles use only valid edges:

[0, 1, 2, 3, 4, 0]
[0, 2, 1, 3, 4, 0]

Therefore, the total count of Hamiltonian cycles for this graph is 2, with the lexicographically first canonical cycle being [0, 1, 2, 3, 4, 0].

Experiment

You can interact with a solver in the Hamiltonian Cycles module.

Enter a sequence of semicolon-separated edge pairs (e.g., 0 1; 1 2; 2 3) into the "Edges" input text field.
Click the "Step" button repeatedly to watch the algorithm sequentially test each candidate permutation for valid edges.
Click the "Finish" button to immediately jump to the end and observe the total Hamiltonian cycle count and the first canonical cycle found in the resulting read-only text fields.

Limitations

The provided module uses a brute-force exhaustive search anchored at vertex 0. This approach is sufficient and deterministic for a small fixed graph (exactly 5 vertices), but it scales poorly. It computes (n - 1)! / 2 candidates, which is why we limit the module to n = 5. This module does not employ heuristic optimizations, does not claim to run in scalable polynomial time, and does not solve the related Traveling Salesperson Problem (TSP) since edges are unweighted.

References

Definitions and distinctions between traversals (Eulerian vs. Hamiltonian) are detailed in primary texts such asApplied Discrete Structures, Section 9.4.

Hamiltonian Cycles