= Balanced component cut
{title2=$\max(|V_1|,|V_2|)\leq(k+1)n/(2k+1)$}
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\leq 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\geq(k+1)(n-2S)$, a contradiction. The proof also works for arbitrary positive weights.
Back to article page
