Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-3/17f/b/solution

Choose a partition that maximizes the number of edges crossing between its two parts. If some had
moving to would replace the former crossing edges incident with by the latter and strictly increase the cut size. This contradicts maximality. The same argument applies to every . 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.

New to topics? Read the docs here!