A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree $k$

Abstract

Erdős, Faudree, Rousseau and Schelp observed the following fact for every fixed integer $k\ge 2$: Every graph on $n\ge k-1$ vertices with at least $(k-1)(n-k+2)+\left(\genfrac{}{}{0ex}{}{k-2}{2}\right)$ edges contains a subgraph with minimum degree at least $k$. However, there are examples in which the whole graph is the only such subgraph. Erdős et al. conjectured that having just one more edge implies the existence of a subgraph on at most $(1-{\epsilon }_k)n$ vertices with minimum degree at least $k$, where ${\epsilon }_k>0$ depends only on $k$. We prove this conjecture, using and extending ideas of Mousset, Noever and Škorić.

arXiv comment34 pages, minor revisions