SOLVED
This has been resolved in some other way than a proof or disproof.
Let $\epsilon>0$. Is there a constant $C_\epsilon$ such that, for all large $n$, every graph on $n$ vertices with at least $n^{1+\epsilon}$ edges must contain a subgraph on at most $C_\epsilon$ vertices which is non-planar?
Erdős
[Er71] writes it is 'not difficult to see' that $C_\epsilon\to \infty$ as $\epsilon\to 0$.
This was solved in the affirmative by Kostochka and Pyber
[KoPy88], who proved that $G$ must contain a subdivision of $K_5$ (which is non-planar) with $O_\epsilon(1)$ many vertices.
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 #1018, https://www.erdosproblems.com/1018, accessed 2026-01-16
