Problem 23

Erdős Problem #23 [status: falsifiable; formalized: yes]. Can every triangle-free graph on $5n$ vertices be made bipartite by deleting at most $n^2$ edges? Current best: 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. Prize: no. OEIS: A389646. Tags: graph theory.