文摘
We prove that, for large n, every 3-connected D-regular graph on n vertices with class="mathmlsrc">class="formulatext stixSupport mathImg" data-mathURL="/science?_ob=MathURL&_method=retrieve&_eid=1-s2.0-S0095895615001380&_mathId=si1.gif&_user=111111111&_pii=S0095895615001380&_rdoc=1&_issn=00958956&md5=b3101202308de778224f4c70a7242a43" title="Click to view the MathML source">D≥n/4class="mathContainer hidden">class="mathCode"> is Hamiltonian. This is best possible and verifies the only remaining case of a conjecture posed independently by Bollobás and Häggkvist in the 1970s. The proof builds on a structural decomposition result proved recently by the same authors.