Hamiltonian paths on Cayley graphs

A Hamiltonian path in a graph $\Gamma$ visits each vertex exactly once; a Hamiltonian cycle closes back to the start. Plugging this into Cayley graphs (§14): a Hamiltonian path is an algorithm that visits every group element exactly once. Can the cube's $4.3\times 10^{19}$ states be traversed by one such alg? An open problem hanging there for over half a century.

29.1 The two conjectures (Cayley + Lovász)

The two protagonists are Cayley (1878) and László Lovász (1970). Cayley's original paper introducing his graphs implicitly asked whether they always carry a Hamiltonian cycle. A century later Lovász formulated a weaker version with "vertex-transitive" replacing "Cayley graph":

Both conjectures remain open, among the oldest unresolved problems in combinatorics. As of 2026, Lovász has been verified by computer for all vertex-transitive graphs of order ≤ 100 (Royle–Spiga); the Cayley cycle conjecture is settled constructively for many infinite families (Abelian, dihedral, generalised quaternion, nilpotent of class 2, …), but no general implication "Cayley ⇒ Hamiltonian cycle" has been proven.

29.2 Petersen graph — vertex-transitive but not Cayley

The classical witness separating the two conjectures is the Petersen graph $P$: 10 vertices, 3-regular, girth (shortest cycle length) 5, diameter 2, vertex-transitive. It is not a Cayley graph of any group — the only 10-element groups are ${\mathbb{Z}}_{10}$ and $D_5$, and neither yields Petersen as a Cayley graph.

29.3 Abelian case — Gray codes

For Abelian groups the Cayley cycle conjecture is true — the cleanest case in the entire conjecture. The proof is constructive, producing an explicit alg. The most elegant example, on ${\mathbb{Z}}_2^n$, is Frank Gray's reflected binary code (Bell Labs, invented 1947, patented 1953): one bit flips per step.

This yields $2^n$ distinct n-bit strings forming a Hamiltonian cycle of ${\mathbb{Z}}_2^n$, each edge corresponding to a generator $e_i$. For a general finite Abelian group $G=\mathbb{Z}/n_1\times \cdots \times \mathbb{Z}/n_k$, use a zig-zag (snake) Gray code: walk $\mathbb{Z}/n_1$ forward, the second row of $\mathbb{Z}/n_2$ backward, the third forward, etc. Total length $\prod n_i=|G|$ gives a Hamilton path; it closes to a cycle when each $n_i\ge 2$ and at least one is even.

The Gray code is not unique. The whole family of sequences where "consecutive strings differ in one bit" is large. Balanced Gray codes require each bit-position to flip nearly equally often (ideally $2^n/n$ times) — used in ADCs to spread spike errors; monotone Gray codes walk by ascending popcount — used in parallel algorithms; snake-in-the-box codes are induced paths of length ≤ $2^n$ (no chord between non-consecutive vertices) — used in error correction. All are Hamiltonian paths or cycles in $\mathrm{Cay}({\mathbb{Z}}_2^n)$, distinguished only by which extra structure is imposed.

29.4 The hypercube Q_n — geometric source of Gray codes

The Cayley graph of ${\mathbb{Z}}_2^n$ with the standard basis is the n-dimensional hypercube $Q_n$: $2^n$ vertices = bit-strings, adjacent iff one bit differs. The reflected Gray code is a Hamiltonian cycle of $Q_n$; conversely every Hamilton cycle of $Q_n$ corresponds to some Gray-style code.

29.5 Knight's tour — the 18th-century prototype

The earliest famous instance of the Hamiltonian path problem — predating Hamilton's 1857 octahedron puzzle by centuries — is the knight's tour: can a knight visit every square of an 8 × 8 board exactly once? The answer "yes" goes back to 9th-century Arabic manuscripts; Euler (1759) gave the first systematic algorithm and Vandermonde (1771) cast it as a combinatorial problem. The knight graph is not a Cayley graph (no transitive group action), but it spawned the entire research direction of Hamilton cycles on regular-ish graphs.

The knight's tour was fully classified in the 20th century (Schwenk 1991): a rectangular m × n board (m ≤ n) admits a closed Hamilton tour iff it does NOT lie in the three exceptional families: mn odd, m ∈ {1, 2, 4}, or m, n ∈ {(3, 4), (3, 6), (3, 8)}. 8 × 8 escapes, so closed tours exist; in fact many — Löbbing–Wegener (1995) computed by BDD that there are exactly 26 534 728 821 064 undirected closed knight's tours (8× more if directed = 2.12 × 10¹⁴).

29.6 Rapaport-Strasser · dihedral and generalised quaternion

In 1959 Elvira Rapaport-Strasser gave the first constructive proof of the Cayley cycle conjecture for a non-Abelian family — the dihedral groups $D_n$ ($2n$ elements, generated by a rotation $r$ and reflection $s$) — showing every connected Cayley graph admits a Hamilton cycle. In 1963 she extended this to generalised quaternion groups $Q_{2^k}$ and several larger finite group families.

After Rapaport-Strasser, results piled up across group families: Witte (1986) for p-groups; Witte-Gallian (1984) for semidirect products ${\mathbb{Z}}_p⋊{\mathbb{Z}}_q$; Chen-Quimpo (1980s) for dihedral × Abelian. A unifying motto: "if every quotient in a normal series $H_0⊲H_1⊲\cdots ⊲G$ has a Hamilton cycle then so does $G$" — the formalisation of §29.9's coset-chaining recipe.

29.7 Marušič 1985 and the modern frontier

From the 1980s onwards Dragan Marušič (the Slovenian school) pushed Lovász's weaker conjecture (vertex-transitive → Hamilton path) upward order by order. His seminal 1983 paper introduced the systematic toolkit — imprimitive block systems, orbital partitions, semiregular automorphisms — that still dominates the field today.

The 2009 Kutnar–Marušič survey arranged all known results in a table ordered by group order. By publication time, every $|G|\le 100$ had been verified; 2012-2018 work (Witte, Verret, Spiga, ...) pushed the line to roughly $|G|\le 200$. Group families now classified as "done":

• all Abelian groups (classical)
• dihedral $D_n$, generalised quaternion $Q_{2^k}$ (Rapaport-Strasser)
• all p-groups (Witte 1986)
• nilpotent groups of class ≤ 2
• all vertex-transitive graphs of order $\le 200$ (Royle-Spiga 2018)
• symmetric groups $S_n$ with transposition generators (Rankin 1948; Compton-Williamson 1991)

A uniform proof remains elusive. Babai (1995), in his survey calling the Cayley conjecture "one of the most important open problems in combinatorics", argued that if Lovász is true there should be a structural group-theoretic reason, not just family-by-family case work. Ten years on, no such reason has emerged. Brute-force computer searches, conversely, give strong evidence: no counterexample has been found.

29.8 Status on cube subgroups

Cube-related groups occupy an interesting position on this problem — some are solved (with explicit constructions), others remain open. Jaap Scherphuis maintains a list on his classic "puzzle pages":

A scale check: the 3×3×3 Cayley graph has $4.3\times 10^{19}$ vertices ≈ the number of grains of sand on Earth's beaches. Even if "BFS for a Ham cycle" were polynomial, the traversal itself would exceed any conceivable compute cluster. Existing cube solvers (Korf IDA*, Kociemba two-phase, Rokicki BFS) are not Ham-cycle constructions — they are geodesic searches or diameter proofs, fundamentally different problems. A geodesic spans ≤ 20 steps; a Hamilton cycle spans $4.3\times 10^{19}$.

29.9 Coset chaining — the standard construction tool

Every solved non-Abelian case (dihedral, quaternion, p-groups, ...) uses the same core technique: coset chaining. In one line: find a subgroup $H\le G$ with a known Ham cycle, then splice the $[G:H]$ cosets of $G/H$ together like a zipper.

Proof sketch: walk inside $g_{1}H$ along $h_1,\dots ,h_m$, hop to $g_{2}H=g_{1}cH$ via $c$, walk backwards $h_m,\dots ,h_1$, hop to $g_{3}H$, zig-zag until all $k$ cosets are covered. Condition (c) ensures the zig-zag endpoints connect without dead-ending. Total length $mk=|G|$, returning to the start.

For the 3×3×3 cube there is a theoretical pathway: take $H=\mathrm{CO}\cdot \mathrm{EO}$ (corner / edge orientation subgroup, Abelian) and traverse it via a Gray code, then use some "orientation-fixing" connector to hop into the next coset. All the difficulty lies in (c) — finding a connector compatible with the Abelian Gray code on every coset. So far no one has built such a connector for the cube.

29.10 Pak-Radoičić · a near-theorem

Igor Pak and Rados Radoičić (2009) proved a weak form of Lovász: every finite group $G$ has a generating set $S$ with $|S|\le {\log }_2|G|$ such that $\mathrm{Cay}(G,S)$ contains a Hamilton cycle. In other words, "if we get to choose the generators, a Hamilton cycle always exists".

This almost settles the Cayley cycle conjecture — the only gap is "the case when we are not allowed to choose the generators". In cube language: if we're free to pick a non-standard generating set (not $\{F,B,L,R,U,D\}$), we can construct a Hamilton cycle of length 4.3 × 10¹⁹. With the standard WCA 6-face generators, the question is still open.

The Pak-Radoičić proof uses the Classification of Finite Simple Groups (CFSG) as a black box, so it is technically conditional on the 10 000-page CFSG monolith from the 1980s. This is one of the rare combinatorial uses of CFSG.

29.11 Computational complexity · NP-complete in general, open for vertex-transitive

Phrasing the Cayley conjecture as a decision problem: given a finite graph $\Gamma$, is there a Hamilton cycle? On general graphs this is one of Karp's 21 NP-complete problems (1972) — computationally intractable in the worst case. With the "vertex-transitive" symmetry constraint, even the complexity class is unknown:

The complexity of HAM-CYCLE on vertex-transitive / Cayley graphs is equivalent to the truth of Lovász / Cayley conjectures: if true, the problem trivially returns "yes", complexity O(1); if false, "no" instances exist but the upper bound is unknown. A rare meeting of mathematics and computer science — a structural conjecture directly determining the complexity class of a decision problem.

29.12 Summary · from 1759 to 2026

A timeline of §29:

• 1759 — Euler systematises the knight's tour, the first form of the Hamilton path problem.
• 1823 — Warnsdorff's rule: first practical Hamilton-path heuristic.
• 1857 — William Hamilton's "Icosian Game" on the dodecahedron coins the term "Hamilton cycle".
• 1878 — Cayley introduces the Cayley graph, with the implicit cycle conjecture.
• 1898 — Petersen exhibits the 10-vertex counterexample (vertex-transitive, no Ham cycle).
• 1947 / 1953 — Frank Gray's reflected binary code: explicit Ham cycle of ${\mathbb{Z}}_2^n$.
• 1959 — Rapaport-Strasser: Ham cycles in dihedral Cayley graphs, first non-Abelian result.
• 1970 — Lovász conjecture (vertex-transitive → Ham path).
• 1972 — Karp: HAM-CYCLE NP-complete on general graphs.
• 1983 / 1985 — Marušič: vertex-transitive graphs of order pk have Ham paths; introduces imprimitive block methods.
• 1986 — Witte: every p-group Cayley graph has a Ham cycle.
• 1996 — Floppy Cube explicit Ham cycle; Rubik's Clock base-12 Gray code.
• 2009 — Kutnar-Marušič survey; Pak-Radoičić near-theorem (via CFSG).
• 2018 — Royle-Spiga: all orders ≤ 200 verified.
• 2026 — Rubik's 3×3×3, Pyraminx, Megaminx still open.

"Can the cube's $4.3\times 10^{19}$ states be walked by one alg?" When Cayley introduced his graph in 1878, the question hadn't even been formulated. A century and a half later we can say it almost certainly has an answer "yes" (Pak-Radoičić, with a non-standard generating set), but for the WCA-standard 6-face / 18-move set — we don't know. Sitting along §14 (Cayley graphs), §28 (chip-firing on game graphs), §29 (this section), this is the central open problem that "geometrising group theory" has left for the 21st century.