= 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 contains
$$
1+3(1+2+\cdots+2^{r-1})=3\cdot2^r-2
$$
vertices. 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\leq100\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$.
Back to article page
