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

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$.

Solved by gpt-5.6-sol high.