Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-2/17g/c/solution
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 2 17G c Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
Choose a bipartition maximizing the number of crossing edges. If the graph has an edge, a maximum cut is nontrivial. Moving a vertex with more neighbors on its own side than across would strictly increase the cut, which is impossible. Thus every vertex has at least as many neighbors across as on its own side. If the graph has no edges, every nontrivial partition works. Hence every graph on at least two vertices has an unfriendly partition.
New to topics? Read the docs here!