Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 1 / c / Solution

Let the blue edges form a graph $B$ on $N$ vertices, and suppose there is no blue copy of $H$. For every vertex $x$, the graph $B[N_B(x)]$ has maximum degree at most one. Indeed, if some $y\in N_B(x)$ had two neighbours $z,w$ inside $N_B(x)$, thenwould be the five blue edges of a copy of $H$.

Let $d=\Delta (B)$. If $d\ge 2k$, then a maximum-degree neighbourhood, being a matching plus isolated vertices, has an independent set of size at least $d/2\ge k$. This is a red $K_k$. We may therefore assume $d<2k$. Part (b) givesIf $d<\sqrt{k}$, the greedy independent-set bound gives $\alpha (B)\ge N/(d+1)>k$ once $N=C{k}^2/\log k$. If $\sqrt{k}\le d<2k$, then part (b) giveswhen $C$ is sufficiently large. In either case there is a red $K_k$, so