Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 3 / a / Solution

A set $R\subseteq V(G)$ is $(s,k)$-rich if every $s$-element subset of $R$ has at least $k$ common neighbours.

Choose $x_1,\dots ,x_t$ independently and uniformly from $V(G)$, with repetition, and putBy convexity,Let $Y$ count the $s$-subsets $S\subseteq W$ having fewer than $k$ common neighbours in $G$. For each such $S$,and thereforeDelete one vertex from every bad $s$-subset of $W$. The remaining set $R$ is $(s,k)$-rich and satisfies $|R|\ge |W|-Y$. The hypothesis givesso some choice has $|R|\ge r$.