A note on balanced bipartitions

A balanced bipartition   of a graph GG is a bipartition V1V1 and V2V2 of V(G)V(G) such that −1≤|V1|−|V2|≤1−1≤|V1|−|V2|≤1. Bollobás and Scott conjectured that if GG is a graph with mm edges and minimum degree at least 2 then GG admits a balanced bipartition V1,V2V1,V2 such that max{e(V1),e(V2)}≤m/3max{e(V1),e(V2)}≤m/3, where e(Vi)e(Vi) denotes the number of edges of GG with both ends in ViVi. In this note, we prove this conjecture for graphs with average degree at least 6 or with minimum degree at least 5. Moreover, we show that if GG is a graph with mm edges and nn vertices, and if the maximum degree Δ(G)=o(n)Δ(G)=o(n) or the minimum degree δ(G)→∞δ(G)→∞, then GG admits a balanced bipartition V1,V2V1,V2 such that max{e(V1),e(V2)}≤(1+o(1))m/4max{e(V1),e(V2)}≤(1+o(1))m/4, answering a question of Bollobás and Scott in the affirmative. We also provide a sharp lower bound on max{e(V1,V2):V1,V2 is a balanced bipartition of G}max{e(V1,V2):V1,V2 is a balanced bipartition of G}, in terms of size of a maximum matching, where e(V1,V2)e(V1,V2) denotes the number of edges between V1V1 and V2V2.