Problem Statement
Let $f(m)$ be the maximal $k$ such that a triangle-free graph on $m$ edges must contain a bipartite graph with $k$ edges. Determine $f(m)$.
Categories:
Graph Theory
Progress
Resolved by Alon [Al96], who showed that there exist constants $c_1,c_2>0$ such that\[\frac{m}{2}+c_1m^{4/5}\leq f(m)\leq \frac{m}{2}+c_2m^{4/5}.\]See also the entry in the graphs problem collection.Source: erdosproblems.com/581 | Last verified: January 15, 2026