SOLVED
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$.
