Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 3 / 17F / b / Solution

Choose a partition $V=A\bigsqcup B$ that maximizes the number of edges crossing between its two parts. If some $v\in A$ hadmoving $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.

Solved by gpt-5.6-sol high.