Chvátal's Toughness Conjecture for Dense Almost Regular Graphs

Chvátal's toughness conjecture asserts that there is a constant t₀ such that every t₀-tough graph on at least three vertices is Hamiltonian. Most partial results on this conjecture concern graphs with a restricted structure, such as chordal graphs and H-free graphs for small linear forests H. We confirm the conjecture with t₀=4 for dense almost regular graphs, without any structural assumption: for every $α>0$, there exist ε>0 and n₀ such that every $4$-tough graph G on n≥ n₀ vertices with δ(G)≥αn and Δ(G)-δ(G)≤ε n is Hamiltonian. This result also bears on a conjecture of Bollobás and, independently, Häggkvist from the 1970s that every k-connected D-regular graph on n vertices with D≥ n/(k+1) is Hamiltonian. This conjecture is false for every k≥4, even for large n. Our result shows that its conclusion holds for all large n when k-connectivity is replaced by $4$-toughness, and that the degree condition can then be weakened to D≥αn for an arbitrarily small fixed $α>0$. We also construct $3/2$-tough regular non-Hamiltonian graphs of linear degree, showing that the constant $4$ cannot be replaced by $3/2$.