r-regular graphs are not uniquely hamiltonian.

High ★★★ Graph Theory » Basic Graph Theory » Cycles

Author: Sheehan, John— posted by Robert Samal on 2007-07-24

Status partial high confidence

The conjecture has been proved for all odd $r$ (Thomason, 1978) and all even $r > 22$ (Haxell–Seamone–Verstraete, 2007), both results predating the OPG posting. Since posting, partial progress includes a proof for 4-regular graphs with sufficiently large automorphism groups (Šajna–Wagner, 2015), a classification of uniquely Hamiltonian vertex-transitive graphs (Miraftab–Morris, 2023/2025), and the structural reduction that 3-connected and 2-connected uniquely Hamiltonian 4-regular graphs are equivalent in existence (Brinkmann–De Pauw, 2024). The primary open case, $r = 4$, remains unresolved.

Cited literature (3)

partial On Sheehan's Conjecture for Graphs with Symmetry (2015)

Mateja Šajna, Andrew Wagner · Journal of Graph Theory · doi:10.1002/jgt.21838

Proves Sheehan's conjecture for 4-regular graphs whose automorphism group has size at least 2n/5 under certain arithmetic conditions on n, a condition weaker than vertex-transitivity.
partial On vertex-transitive graphs with a unique hamiltonian cycle (2025)

Babak Miraftab, Dave Witte Morris · Journal of Graph Theory · arXiv:2303.11124 · doi:10.1002/jgt.23166

Classifies all uniquely Hamiltonian vertex-transitive graphs with finitely many ends, confirming Sheehan's conjecture in the vertex-transitive setting and extending the study to infinite graphs.
partial Uniquely hamiltonian graphs for many sets of degrees (2024)

Gunnar Brinkmann, Matthias De Pauw · arXiv preprint · arXiv:2304.08946

Establishes that 3-connected and 2-connected uniquely Hamiltonian 4-regular graphs are equivalent in existence, and introduces 'seeds' as a structural tool potentially useful for resolving Sheehan's conjecture for r = 4.

Reviewer notes. The key pre-posting results (Thomason 1978 for odd r; Haxell–Seamone–Verstraete 2007 for even r > 22, DOI 10.1002/jgt.20205) are cited in the OPG and were not re-included. The Šajna–Wagner (2015) cited URL is a seminar abstract page, not the journal article, because the Wiley page (10.1002/jgt.21838) returned HTTP 402. The Brinkmann–De Pauw paper venue could not be confirmed beyond 'published December 1, 2024' from the arXiv metadata. A 2025 arXiv paper (2506.21337, Baligacs et al.) introduces 'Hamiltonian-transitive graphs' and generalizes the framework but does not directly resolve the r = 4 case; not cited in since_posted as its relationship to the main conjecture is indirect.

Auto-reviewed 2026-05-08 with claude-sonnet-4-6 (worker 02) (web search enabled).

Conjecture. If $ G $ is a finite $ r $ -regular graph, where $ r > 2 $ , then $ G $ is not uniquely hamiltonian.

Keywords: hamiltonian · regular · uniquely hamiltonian

Discussion

(Reproduced from [M].) A graph $ G $ is said to be uniquely hamiltonian if it contains precisely one Hamiltonian cycle . This conjecture has been proved for all odd values of $ r $ [T] and for all even values of $ r > 23 $ [H]. By Petersen's theorem, it would suffice to prove it for $ r = 4 $ .

Bibliography

[H] P. Haxell, Oberwolfach reports, 2006.
[M] Bojan Mohar, Problem of the Month Problem of the Month
★ [S] John Sheehan: The multiplicity of Hamiltonian circuits in a graph. Recent advances in graph theory (Proc. Second Czechoslovak Sympos., Prague, 1974), pp. 477-480. Academia, Prague, 1975, MathSciNet MathSciNet
[T] A.G. Thomason, Hamiltonian cycles and uniquely edge colourable graphs. Advances in graph theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977). Ann. Discrete Math. 3 (1978), Exp. No. 13, 3 pp.