Longest cycles and Dirac-type results in highly connected graphs

Abstract

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\le 3$ and remains open for all $k\ge 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.