4-connected graphs are not uniquely hamiltonian

Status open medium confidence

The conjecture that every 4-connected Hamiltonian graph has a second Hamilton cycle remains open. Fleischner's companion paper (already cited in the OPG bibliography as 'to appear,' published 2014) constructs uniquely Hamiltonian graphs of minimum degree 4 but with connectivity only 2 or 3, confirming that 4-connectivity is the essential barrier. A 2023–2024 extension by Brinkmann and De Pauw further develops such constructions for many degree sequences while still not surpassing 3-connectivity.

Cited literature (1)

• partial Uniquely hamiltonian graphs for many sets of degrees (2023)
  Gunnar Brinkmann, Matthias De Pauw · arXiv preprint · arXiv:2304.08946

  For all degree sets $M$ with minimum 4, except possibly $\{4\}$, $\{4,5\}$, and $\{4,6\}$, uniquely Hamiltonian graphs with exactly those vertex degrees exist; the best connectivity achieved is 3, leaving the 4-connected case of the conjecture untouched.

Reviewer notes. The Fleischner 2014 J. Graph Theory paper (DOI 10.1002/jgt.21729) is the OPG-cited 'to appear' reference and is treated as background, not new progress. Wiley and Springer journal pages returned 403/redirect errors, preventing direct verification. The related Sheehan conjecture (second Hamilton cycle in 4-regular graphs) is also open. Brinkmann–De Pauw (arXiv:2304.08946) was published in a journal in December 2024 but the journal name was not visible from the abstract page. Eppstein (arXiv:2510.18359, 2025) and Lancia et al. (arXiv:2112.05087, 2021) were verified but are not directly relevant to the 4-connected conjecture.

Auto-reviewed 2026-05-07 with claude-sonnet-4-6 (web search enabled) · 237s.