Almost all non-Hamiltonian 3-regular graphs are 1-connected

Medium ★★ Graph Theory » Basic Graph Theory accessible to undergrads

Author: Haythorpe, Michael— posted by mhaythorpe on 2013-08-23

Status open high confidence

The conjecture that $\lim_{n\to\infty} NHB(n)/NH(n)=1$ (almost all non-Hamiltonian 3-regular graphs are 1-connected, i.e., contain a bridge) remains open. The original 2010 paper by Filar, Haythorpe, and Nguyen provided only computational evidence up to $n=25$, and no subsequent theoretical or computational advance settling or substantially extending this conjecture has been found in the literature through May 2026.

Reviewer notes. The OPG page itself was unreachable (ECONNREFUSED). The Flinders Hamiltonian Cycle Project publications page listed only the original 2010 FHN paper and related computational/heuristic work (a 2015 Computers & Operations Research paper on detecting non-Hamiltonicity, and a 2014 paper on non-Hamiltonian cubic graphs with arbitrary girth), none of which address the NHB(n)/NH(n) ratio conjecture. A candidate 2019 paper by 'Advani' returned by one AI-summarized arXiv fetch could not be verified by direct search and is almost certainly a hallucination; it is not cited. No counterexample, proof, or asymptotic analysis of this specific ratio has been found.

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

Conjecture. Denote by $ NH(n) $ the number of non-Hamiltonian 3-regular graphs of size $ 2n $ , and similarly denote by $ NHB(n) $ the number of non-Hamiltonian 3-regular 1-connected graphs of size $ 2n $ . Is it true that $ \lim\limits_{n \rightarrow \infty} \displaystyle\frac{NHB(n)}{NH(n)} = 1 $ ?

Keywords: Hamiltonian, Bridge, 3-regular, 1-connected

Discussion

A stronger version of this conjecture asks whether it is also the case that $ \displaystyle\frac{NHB(n)}{NH(n)} > \displaystyle\frac{NHB(k)}{NH(k)} $ for all $ n > k $ . Experimental data was given by Filar et al [FHN] demonstrating that the strong conjecture is satisfied for all $ n \leq 12 $ , and with sampled data provided for $ n = 20 $ and $ n = 25 $ . No further results have been forthcoming. The experimental data can be viewed at http://dx.doi.org/10.7151/dmgt.1485 Packers And Movers Chandigarh Packers And Movers Hyderabad Packers And Movers Bangalore

Bibliography

[FHN] Jerzy A Filar, Giang T Nguyen, Michael Haythorpe, "A conjecture on the prevalence of cubic bridge graphs", Discussiones Mathematicae Graph Theory 30(1):175--179 (2010).