Longest cycles and Dirac-type results in highly connected graphs

A classical theorem of Nash-Williams states that if G is a $2$-connected graph on n vertices with minimum degree at least $(n+2)/3$, then for every longest cycle C of G, the graph $G-V(C)$ is edgeless. Motivated by a higher-connectivity analogue, Bondy proposed an Ore-type conjecture in 1980, with the following Dirac-type specialization: if G is a k-connected graph on n vertices with minimum degree at least $(n+k(k-1))/(k+1)$, then for every longest cycle C of G, every path in $G-V(C)$ has at most $k-1$ vertices. This conjecture has been proved for k≤ 3 and remains open for all k≥ 4. In this paper, we prove the Dirac-type specialization of Bondy’s conjecture for all sufficiently large graphs. The key ingredient is a new Dirac-type theorem that gives a lower bound on the length of a longest cycle in a k-connected graph, which also yields a partial solution to a conjecture of Jung from 1990. Along the way, we develop several new tools, including a depth-first search (DFS) lemma and an average-degree analogue of the Bondy–Jackson theorem. We conclude with a discussion of related problems and a counterexample to a conjecture of Voss from 1991.