Graph cut ($\partial S=\{\{i,j\}\in E:i\in S,j\notin S\}$)

A graph cut consists of the edges joining a vertex subset to its complement. In a two-group stochastic block model, crossing and within-group edges have different Bernoulli distributions. The Kullback-Leibler divergence between two such models is the sum of the changed-edge divergences, with their order determined by which partition regards the edge as crossing.

If every graph component has at most $(k+1)n/[k(2k+1)]$ vertices, assigning whole graph components to two sides gives an empty graph cut with the displayed bound. To prove it, maximize the smaller side's weight $S\le n/2$. If $S<kn/(2k+1)$, every component on the larger side has weight at least $n-2S$, because moving a smaller one would improve the smaller side. There are at least $k+1$ such components, since their total exceeds $k$ times the permitted maximum weight. Thus $n-S\ge (k+1)(n-2S)$, a contradiction. The proof also works for arbitrary positive weights.