Balanced bipartite distance of $K_4$-free graphs

József Balogh, Ignacy Buczek, Andrzej Grzesik +1

We show that every $K_4$-free graph on $n$ vertices can be made balanced bipartite by removing at most $\frac{n^2}{9}$ edges. This proves a conjecture of Balogh, Clemen, and Lidick…