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
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
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-04-11
