{"id":"arxiv/2606.03696","url":"https://arxiv.org/abs/2606.03696","tags":["math.CO"],"score":0,"title":"Longest cycles and Dirac-type results in highly connected graphs","domain":"math.CO","source":"arxiv","authors":["Jie Ma","Bo Ning","Ziyuan Zhao"],"reviews":0,"subject":"math.CO","summary":"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 conjectured in 1980 that 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 is known for $k\\le 3$ and remains open for all $k\\ge 4$. In this paper, we prove Bondy's conjecture for all…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-06-02","reactions":{}}