Extensions of the Erdős–Gallai theorem and Luo’s theorem
Extensions of the Erdős–Gallai theorem and Luo’s theorem
The famous Erd\H{o}s-Gallai Theorem on the Tur\'an number of paths states that every graph with $n$ vertices and $m$ edges contains a path with at least $\frac{2m}{n}$ edges. In this note, we first establish a simple but novel extension of the Erd\H{o}s-Gallai Theorem by proving that every graph $G$ contains …