Stability in the Erdős--Gallai Theorem on cycles and paths, II

Abstract

The Erdős--Gallai Theorem states that for $k\ge 3$, any $n$-vertex graph with no cycle of length at least $k$ has at most $\frac{1}{2}(k-1)(n-1)$ edges. A stronger version of the Erdős--Gallai Theorem was given by Kopylov: If $G$ is a 2-connected $n$-vertex graph with no cycle of length at least $k$, then $e(G)\le \max \{h(n,k,2),h(n,k,\lfloor \frac{k-1}{2}\rfloor )\}$, where $h(n,k,a):=\left(\genfrac{}{}{0ex}{}{k-a}{2}\right)+a(n-k+a)$. Furthermore, Kopylov presented the two possible extremal graphs, one with $h(n,k,2)$ edges and one with $h(n,k,\lfloor \frac{k-1}{2}\rfloor )$ edges. In this paper, we complete a stability theorem which strengthens Kopylov's result. In particular, we show that for $k\ge 3$ odd and all $n\ge k$, every $n$-vertex $2$-connected graph $G$ with no cycle of length at least $k$ is a subgraph of one of the two extremal graphs or $e(G)\le \max \{h(n,k,3),h(n,k,\frac{k-3}{2})\}$. The upper bound for $e(G)$ here is tight.