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].

View the LaTeX source