Smaller subgraphs of minimum degree k

Abstract

In 1990 Erdős, Faudree, Rousseau and Schelp proved that for $k\ge 2$, every graph with $n\ge k+1$ vertices and $(k-1)(n-k+2)+\left(\genfrac{}{}{0ex}{}{k-2}{2}\right)+1$ edges contains a subgraph of minimum degree $k$ on at most $n-\sqrt{n}/\sqrt{6k^3}$ vertices. They conjectured that it is possible to remove at least ${\epsilon }_{k}n$ many vertices and remain with a subgraph of minimum degree $k$, for some ${\epsilon }_k>0$. We make progress towards their conjecture by showing that one can remove at least $\Omega (n/\log n)$ many vertices.