On judicious bisections of graphs

A bisection of a graph G   is a bipartition S1S1, S2S2 of V(G)V(G) such that −1⩽|S1|−|S2|⩽1−1⩽|S1|−|S2|⩽1. It is NP-hard to find a bisection S1S1, S2S2 of a graph G   maximizing e(S1,S2)e(S1,S2) (respectively, minimizing max{e(S1),e(S2)}max{e(S1),e(S2)}), where e(S1,S2)e(S1,S2) denotes the number of edges of G   between S1S1 and S2S2, and e(Si)e(Si) denotes the number of edges of G   with both ends in SiSi. There has been algorithmic work on bisections, but very few extremal results are known. Bollobás and Scott conjectured that if G is a graph with m edges and minimum degree at least 2 then G   admits a bisection S1,S2S1,S2 such that max{e(S1),e(S2)}⩽m/3max{e(S1),e(S2)}⩽m/3. In this paper, we confirm this conjecture and show that the triangle is the only extremal graph. Moreover, the bound m/3m/3 cannot be improved to (1/3−ϵ)m(1/3−ϵ)m, for any ϵ>0ϵ>0, by excluding K3K3 or by increasing the minimum degree from 2 to 3.