Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 2 / 17G (Graph Theory)

A tree is a connected acyclic graph; acyclic means containing no cycle. Every component of an acyclic graph is a tree. If the component orders are $n_i$, each has $n_i-1$ edges, so with $c\ge 1$ components,

If a cubic graph has no cycle of length at most $2r+1$, the Breadth-first search ball of radius $r$ about a vertex is a tree and containsvertices. Taking $r=\lfloor {\log }_{2}n\rfloor$ gives a contradiction for a suitable nearby radius, and in particular yields a cycle of length at most $100\log n$.

Choose such a cycle $C$ of length $m\le 100\log n$. Removing its vertices deletes at most $3m$ edges. The remaining graph has at least $3n/2-3m$ edges on $n-m$ vertices. For all sufficiently large $n$, this exceeds $n-m-1$, so part (a) says the remainder contains a cycle. It is vertex-disjoint from $C$.

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.

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.