## Abstract

The Erdős–Gallai Theorem states that for k≥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≥5, n≥(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=H_{n,k,t}:=K_{n}−E(K_{n−t}). In this paper we prove a stability version of the Erdős–Gallai Theorem: we show that for all n≥3t>3, and k∈{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≠7, we show G⊆H_{n,k,t}. The lower bound 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).

Original language | English (US) |
---|---|

Pages (from-to) | 197-228 |

Number of pages | 32 |

Journal | Journal of Combinatorial Theory. Series B |

Volume | 121 |

DOIs | |

State | Published - Nov 1 2016 |

## Keywords

- Cycles
- Paths
- Turán problem

## ASJC Scopus subject areas

- Theoretical Computer Science
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics