Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-3/17f/b/solution
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 3 17F b Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Choose a partition that maximizes the number of edges crossing between its two parts. If some hadmoving 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!