Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2 / 17G / d / Solution

The complete graph $K_4$ is cubic and has no friendly partition: a $1+3$ split fails at the singleton, while in a $2+2$ split every vertex has one neighbor on its own side and two across.

For a sufficiently large cubic graph, part (b) supplies disjoint cycles $C_1,C_2$. Put $C_1$ initially in $S$ and $C_2$ in $T$, 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.

Solved by gpt-5.6-sol high.