Does every connected Cayley graph on a finite group have a Hamiltonian cycle? (The Cayley graph Hamiltonicity conjecture)

It is a famous open problem, going back to questions of Lovász (1969) on vertex-transitive graphs, whether every connected Cayley graph on an arbitrary finite group contains a Hamiltonian cycle. The source paper (Maghsoudi, arXiv:2009.10055) proves only the special order classes $|G|=6pq$ and $7pq$, and explicitly acknowledges the general question as open. The general conjecture remains open: no proof or counterexample is known for the unrestricted statement.

Background

A Cayley graph is a graph built from a group: for a finite group $G$ and a subset $S$ of $G$, the graph $\mathrm{Cay}(G;S)$ has the elements of $G$ as its vertices, with an edge joining $g$ and $gs$ for every $g$ in $G$ and $s$ in $S$. When $S$ generates $G$ (and, for undirected graphs, $S$ is closed under inverses), the graph $\mathrm{Cay}(G;S)$ is connected and highly symmetric: it is vertex-transitive, meaning every vertex looks like every other vertex because left multiplication by any group element is a graph automorphism. A Hamiltonian cycle is a closed walk that visits every vertex of the graph exactly once and returns to its start; a Hamiltonian path is the same without the return step. Whether highly symmetric graphs must be Hamiltonian is a classical theme: in 1969 Lovász asked whether every finite connected vertex-transitive graph contains a Hamiltonian path (a variant recorded and popularized in the standard surveys of Witte–Gallian 1984 and Curran–Gallian 1996), and the cycle version for Cayley graphs became one of the central open problems of algebraic graph theory. Only five connected vertex-transitive graphs without a Hamiltonian cycle are known (the complete graph $K_2$, the Petersen graph and the Coxeter graph — classical 3-regular vertex-transitive graphs on 10 and 28 vertices respectively — and two graphs obtained from the Petersen and Coxeter graphs by replacing each vertex with a triangle), and none of them is a Cayley graph; Thomassen conjectured that only finitely many such graphs exist, while Babai conjectured infinitely many. Many positive classes are known: connected Cayley graphs on abelian groups, on groups of prime-power order, and on groups whose order has few prime factors are Hamiltonian; a July 2026 tabulation (Lehner–Maghsoudi–Miraftab) records that every connected Cayley graph on a group of order $kp$ for $1\le k\le 47$, $kpq$ for $1\le k\le 9$, $pqr$, $pqrs$ with $p,q,r,s$ distinct odd primes, $kp^2$ for $1\le k\le 4$, $kp^3$ for $1\le k\le 2$, or $p^k$ for $1\le k<8$ has a Hamiltonian cycle, and the same paper's main theorem removes the oddness restriction, establishing the $pqrs$ case for arbitrary distinct primes. For dense Cayley graphs, Christofides–Hladký–Máthé (2014) and Bedert–Draganić–Müyesser–Pavez-Signé (2026) proved Hamiltonicity by analytic methods, the latter showing that every sufficiently large connected $n$-vertex Cayley graph of degree at least $n^{1-c}$, for an absolute constant $c>0$, has a Hamilton cycle. Pak–Radoičić (2009) proved the relaxation that every connected Cayley graph on at least three vertices contains a Hamiltonian path. Despite all this, no technique is known that handles a general finite group with an arbitrary generating set, and no candidate counterexample exists. As the source paper states (ignoring the trivial groups of order 1 or 2, where no cycle exists), 'it is still an open question whether every connected Cayley graph has a Hamiltonian cycle.'

Problem Statement

Does every connected Cayley graph on a finite group contain a Hamiltonian cycle? Equivalently: is it true that for every finite group $G$ with $|G|\ge 3$ and every inverse-closed generating set $S$ of $G$ (i.e. $S=S^{-1}$, so the graph is undirected), with the identity not in $S$, the Cayley graph $\mathrm{Cay}(G;S)$ contains a Hamiltonian cycle? A positive answer (proof for all finite groups) resolves the conjecture; an explicit finite group $G$ and generating set $S$ with $\mathrm{Cay}(G;S)$ connected but non-Hamiltonian refutes it. No restriction on group order, group structure, generating-set size, or graph degree may be imposed; the trivial groups of order at most 2, on which no Hamiltonian cycle exists, are excluded as in the source formulation.

References

1. Farzad Maghsoudi, Cayley graphs of order 6pq are Hamiltonian, arXiv:2009.10055 (v1 2020, v4 2025), DOI 10.48550/arXiv.2009.10055, https://arxiv.org/abs/2009.10055 (source paper)
2. Farzad Maghsoudi, Cayley graphs of order 6pq and 7pq are Hamiltonian, The Art of Discrete and Applied Mathematics 5(1), Paper No. P1.10 (2022), DOI 10.26493/2590-9770.1389.fa2, https://doi.org/10.26493/2590-9770.1389.fa2 (published journal version of the source paper)
3. David Witte and Joseph A. Gallian, A survey: Hamiltonian cycles in Cayley graphs, Discrete Mathematics 51 (1984) 293–304, DOI 10.1016/0012-365X(84)90010-4, https://doi.org/10.1016/0012-365X(84)90010-4
4. Stephen J. Curran and Joseph A. Gallian, Hamiltonian cycles and paths in Cayley graphs and digraphs — A survey, Discrete Mathematics 156 (1996) 1–18, DOI 10.1016/0012-365X(95)00072-5, https://doi.org/10.1016/0012-365X(95)00072-5
5. Igor Pak and Radoš Radoičić, Hamiltonian paths in Cayley graphs, Discrete Mathematics 309 (2009) 5501–5508, DOI 10.1016/j.disc.2009.02.018, https://doi.org/10.1016/j.disc.2009.02.018
6. Demetres Christofides, Jan Hladký, and András Máthé, Hamilton cycles in dense vertex-transitive graphs, Journal of Combinatorial Theory, Series B 109 (2014) 34–72, DOI 10.1016/j.jctb.2014.05.001, https://doi.org/10.1016/j.jctb.2014.05.001
7. Dave Witte Morris and Kirsten Wilk, Cayley graphs of order kp are hamiltonian for k < 48, arXiv:1805.00149 (2018; v2 2023); published as The Art of Discrete and Applied Mathematics 3(2), Paper No. 2.02 (2020), DOI 10.26493/2590-9770.1250.763, https://arxiv.org/abs/1805.00149
8. Fateme Abedi, Dave Witte Morris, Javanshir Rezaee, and M. Reza Salarian, Cayley graphs of order 8pq are hamiltonian, arXiv:2304.03348 (2023); published in Contributions to Discrete Mathematics 20(2) (2025) 311–336, DOI 10.55016/ojs/cdm.v20i2.77376, https://arxiv.org/abs/2304.03348
9. Florian Lehner, Farzad Maghsoudi, and Babak Miraftab, Hamiltonicity of Transitive Graphs Whose Automorphism Group Has $\mathbb{Z}_{p}$ as Commutator Subgroups, arXiv:2412.08105 (2024); published in Discrete Mathematics 349(3), article 114798 (2026), DOI 10.1016/j.disc.2025.114798, https://doi.org/10.1016/j.disc.2025.114798
10. Misa Nakanishi, Proof of Lovász conjecture for odd order, arXiv:2407.00646 (2024), DOI 10.48550/arXiv.2407.00646, https://arxiv.org/abs/2407.00646 (unverified preprint claim; not peer-reviewed)
11. Benjamin Bedert, Nemanja Draganić, Alp Müyesser, and Matías Pavez-Signé, The Lovász conjecture holds for moderately dense Cayley graphs, arXiv:2603.08675 (2026), DOI 10.48550/arXiv.2603.08675, https://arxiv.org/abs/2603.08675
12. Florian Lehner, Farzad Maghsoudi, and Bobby Miraftab, Cayley Graphs Of Order $pqrs$ Are Hamiltonian, arXiv:2607.14440 (2026), DOI 10.48550/arXiv.2607.14440, https://arxiv.org/abs/2607.14440