A Strengthening of Erdős-Gallai Theorem and Proof of Woodall's Conjecture

Abstract

For a 2-connected graph $G$ on $n$ vertices and two vertices $x,y\in V(G)$, we prove that there is an $(x,y)$-path of length at least $k$ if there are at least $\frac{n-1}{2}$ vertices in $V(G)\backslash \{x,y\}$ of degree at least $k$. This strengthens a well-known theorem due to Erdős and Gallai in 1959. As the first application of this result, we show that a 2-connected graph with $n$ vertices contains a cycle of length at least $2k$ if it has at least $\frac{n}{2}+k$ vertices of degree at least $k$. This confirms a 1975 conjecture made by Woodall. As another applications, we obtain some results which generalize previous theorems of Dirac, Erdős-Gallai, Bondy, and Fujisawa et al., present short proofs of the path case of Loebl-Komlós-Sós Conjecture which was verified by Bazgan et al. and of a conjecture of Bondy on longest cycles (for large graphs) which was confirmed by Fraisse and Fournier, and make progress on a conjecture of Bermond.

16 pages, to appear in Journal of Combinatorial Theory, Series B