Erdős Problem #814

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\).