= 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)$, then
$$
xy,xz,xw,yz,yw
$$
would be the five blue edges of a copy of $H$.
Let $d=\Delta(B)$. If $d\ge2k$, 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) gives
$$
\alpha(B)\ge c\frac{N\log d}{d}.
$$
If $d<\sqrt{k}$, the <greedy independent-set bound> gives $\alpha(B)\ge N/(d+1)>k$ once $N=Ck^2/\log k$. If $\sqrt{k}\le d<2k$, then part (b) gives
$$
\alpha(B)\ge c'\frac{N\log k}{k}\ge k
$$
when $C$ is sufficiently large. In either case there is a red $K_k$, so
$$
\boxed{r(H,K_k)\le Ck^2/\log k.}
$$
Back to article page
