Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2021/ii/paper-2/17g/d/solution
Past exam of the mathematics course of the University of Cambridge 2021 ii Paper 2 17G d Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
The complete graph is cubic and has no friendly partition: a split fails at the singleton, while in a split every vertex has one neighbor on its own side and two across.
For a sufficiently large cubic graph, part (b) supplies disjoint cycles . Put initially in and in , and assign all remaining vertices to maximize the number of edges lying within a part. Every cycle vertex already has two same-side neighbors. Any other vertex with more opposite-side than same-side neighbors could be moved to increase the objective. Thus the final nonempty partition is friendly.
New to topics? Read the docs here!