Stability in the Erdős–Gallai Theorems on cycles and paths

The Erdős–Gallai Theorem states that for k≥2k≥2, every graph of average degree more than k−2k−2 contains a k-vertex path. This result is a consequence of a stronger result of Kopylov: if k   is odd, k=2t+1≥5k=2t+1≥5, n≥(5t−3)/2n≥(5t−3)/2, and G is an n  -vertex 2-connected graph with at least h(n,k,t):=(k−t2)+t(n−k+t) edges, then G contains a cycle of length at least k   unless G=Hn,k,t:=Kn−E(Kn−t)G=Hn,k,t:=Kn−E(Kn−t).In this paper we prove a stability version of the Erdős–Gallai Theorem: we show that for all n≥3t>3n≥3t>3, and k∈{2t+1,2t+2}k∈{2t+1,2t+2}, every n-vertex 2-connected graph G   with e(G)>h(n,k,t−1)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≠7k=2t+1≠7, we show G⊆Hn,k,tG⊆Hn,k,t. The lower bound e(G)>h(n,k,t−1)e(G)>h(n,k,t−1) in these results is tight and is smaller than Kopylov's bound h(n,k,t)h(n,k,t) by a term of n−t−O(1)n−t−O(1).