PROVED
This has been solved in the affirmative.
Let $k\geq 2$ and $G$ be a graph with $n\geq k-1$ vertices and\[(k-1)(n-k+2)+\binom{k-2}{2}+1\]edges. Does there exist some $c_k>0$ such that $G$ must contain an induced subgraph on at most $(1-c_k)n$ vertices with minimum degree at least $k$?
The case $k=3$ was a problem of Erdős and Hajnal
[Er91]. The question for general $k$ was a conjecture of Erdős, Faudree, Rousseau, and Schelp
[EFRS90], who proved that such a subgraph exists with at most $n-c_k\sqrt{n}$ vertices. Mousset, Noever, and Skorić
[MNS17] improved this to\[n-c_k\frac{n}{\log n}.\]The full conjecture was proved by Sauermann
[Sa19], who proved this with $c_k \gg 1/k^3$.
View the LaTeX source
Additional thanks to: Zach Hunter
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #814, https://www.erdosproblems.com/814, accessed 2026-01-16
