Problem Statement
Is there some constant $C>0$ such that any graph on $n$ vertices with $\geq Cr^2n$ edges contains a subdivision of $K_r$?
Categories:
Graph Theory
Progress
A conjecture of Erdős, Hajnal, and Mader. Dirac [Di60] proved that every graph on $n$ vertices with at least $2n-2$ edges contains a subdivision of $K_4$, and conjectured that $3n-5$ edges forces a subdivision of $K_5$.Mader [Ma67] proved that $\geq 2^{\binom{r}{2}}n$ edges suffices.
The answer is yes, proved independently by Komlós and Szemerédi [KoSz96] and Bollobás and Thomason [BoTh96].
Source: erdosproblems.com/718 | Last verified: January 16, 2026