FALSIFIABLE
Open, but could be disproved with a finite counterexample.
Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges?
The blow-up of $C_5$ shows that this would be the best possible. The best known bound is due to Balogh, Clemen, and Lidicky
[BCL21], who proved that deleting at most $1.064n^2$ edges suffices.
In
[Er92b] Erdős asks, more generally, if a graph on $(2k+1)n$ vertices in which every odd cycle has size $\geq 2k+1$ can be made bipartite by deleting at most $n^2$ edges.
See also
the entry in the graphs problem collection.
View the LaTeX source
Additional thanks to: Casey Tompkins
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 #23, https://www.erdosproblems.com/23, accessed 2025-11-16
