Upper bounds on minimum balanced bipartitions

A balanced bipartition of a graph GG is a partition of V(G)V(G) into two subsets V1V1 and V2V2, which differ in size by at most 11. The minimum balanced bipartition problem asks for a balanced bipartition V1,V2V1,V2 of a graph minimizing e(V1,V2)e(V1,V2), where e(V1,V2)e(V1,V2) is the number of edges joining V1V1 and V2V2. We present a tight upper bound on the minimum of e(V1,V2)e(V1,V2), giving one answer to a question of Bollobás and Scott. We prove that every connected triangle-free plane graph GG of order at least 3 has a balanced bipartition V1,V2V1,V2 with e(V1,V2)≤|V(G)|−2e(V1,V2)≤|V(G)|−2, and we show that K1,3K1,3, K3,3−eK3,3−e, and K2,nK2,n, with n≥1n≥1, are precisely the extremal graphs. We also show that every plane graph GG without separating triangles has a balanced bipartition V1,V2V1,V2 such that e(V1,V2)≤|V(G)|+1e(V1,V2)≤|V(G)|+1.