Stability in the Erdos--Gallai Theorem on cycles and paths

The Erd\H{o}s-Gallai Theorem states that for $k\ge 2$, every graph of average degree more than $k-2$ contains a $k$-vertex path. This result is a consequence of a stronger result of Kopylov: if $k$ is odd, $k=2t+1\ge 5$, $n \geq (5t-3)/2$,and$G$isan$n$-vertex$2$-connectedgraphwithatleast$h(n,k,t) := {k-t \choose 2} + t(n -k+ t)$edges,then$G$ contains a cycle of length at least $k$ unless $G=H_{n,k,t}:=K_n-E(K_{n-t})$. In this paper we prove a stability version of the Erd\H{o}s-Gallai Theorem: we show that for all $n\ge 3t>3$, and $k\in \{2t+1,2t+2\}$, every $n$-vertex 2-connected graph $G$ with $e(G)>h(n,k,t-1)$ either contains a cycle of length at least $k$ or contains a set of $t$ vertices whose removal gives a star forest. In particular, if $k=2t+1\mathrm{\ne }7$, we show $G \subseteq H_{n,k,t}$\mathrm{.}Thelowerbound$e(G) > h(n,k,t-1)$ in these results is tight and is smaller than Kopylov’s bound $h(n,k,t)$ by a term of $n-t-O(1)$.