Past exam of the mathematics course of the University of Cambridge / 2012 / iii / Paper 9 / 2 / i / Solution

Let $a=kn/(2k+1)$, $u=(k+1)n/(2k+1)$ and $b=u/k$. A graph cut with no crossing edges is obtained by assigning whole graph components to its two sides. Among all such assignments, maximize the smaller side's size $S\le n/2$, and write $T=n-S$ for the other side.

Suppose $S<a$. Then $T>u=kb$. If a graph component on the larger side had size $0<w<n-2S$, moving it to the smaller side would make both $S+w$ and $T-w$ greater than $S$. That contradicts maximality. Hence every graph component on the larger side has at least $n-2S$ vertices. Since each has at most $b$ vertices and their total exceeds $kb$, there must be at least $k+1$ of them. Consequentlya contradiction. Thus $a\le S\le T\le u$, proving the required empty cut with both sides at most $(k+1)n/(2k+1)$. This balanced component cut argument works for arbitrary positive component weights as well; it does not require divisibility of $n$.