Originally asked by Bollobás and Erdős in 'a colloquium on graph theory at Tihany' with $m^{2/3}$ replaced by $m^{3/4}$. Folkman showed this is false with the counterexample $K_{n,n^2}$, which has $n^3$ edges, and yet every subgraph with $>n^2+\binom{n}{2}$ edges contains a $C_4$.

In [Er71] Erdős revises the conjecture to $m^{2/3}$, and notes $\gg m^{1/2}$ is trivial. In a footnote he says Szemerédi proved this conjecture, but gives no reference, and I could not find such a result in the literature.

This problem was first solved in the affirmative by Conlon, Fox, and Sudakov [CFS14b]. A simple proof is given by Hunter in the comments.

View the LaTeX source

This page was last edited 27 December 2025.