= 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\leq 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. Consequently
$$
n-S=T\geq(k+1)(n-2S),\qquad S\geq\frac{kn}{2k+1}=a,
$$
a contradiction. Thus $a\leq S\leq T\leq u$, proving the \b[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$.
Back to article page
