= Solution
Choose a <cut of a graph>[partition] $V=A\sqcup B$ that maximizes the number of edges crossing between its two parts. If some $v\in A$ had
$$
|N(v)\cap B|<|N(v)\cap A|,
$$
moving $v$ to $B$ would replace the former crossing edges incident with $v$ by the latter and strictly increase the cut size. This contradicts maximality. The same argument applies to every $v\in B$. Hence every vertex has at least as many neighbours in the opposite part as in its own part, so the maximum cut is an <unfriendly partition of a graph>.
Back to article page
