PROVED
This has been solved in the affirmative.
Let $f(m)$ be maximal such that every graph with $m$ edges must contain a bipartite graph with\[\geq \frac{m}{2}+\frac{\sqrt{8m+1}-1}{8}+f(m)\]edges. Is there an infinite sequence of $m_i$ such that $f(m_i)\to \infty$?
Conjectured by Erdős, Kohayakava, and Gyárfás. Edwards
[Ed73] proved that $f(m)\geq 0$ always. Note that $f(\binom{n}{2})= 0$, taking $K_n$. Solved by Alon
[Al96], who showed $f(n^2/2)\gg n^{1/2}$, and also showed that $f(m)\ll m^{1/4}$ for all $m$. The best possible constant in $f(m)\leq Cm^{1/4}$ is unknown.
View the LaTeX source
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 #127, https://www.erdosproblems.com/127, accessed 2026-01-16
