Balanced graphs with edge density constraints
J. Sheehan · Journal of Graph Theory · 1990
Abstract Suppose that G is a finite simple graph with |V(G)| = 2n (n ≠ 3). a partition (X,Y) of V(G) is balanced if (i) |X| = |Y| = n, (ii) δ(X) ≥ 1, δ(Y) ≥ 1. Where δ(X) is the minimum degree of the induced subgraph 〈X〉 with vertex set X. We prove that if |E(G)| ≥ (n2 + n + 2)/2 and G is connected, then G contains a balanced partition. The result is sharp.