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

Choose a bipartition $V(H)=A\bigsqcup B$ and inject $A$ into the $(d,k)$-rich set $R$. For each $b\in B$, the images of its neighbours form a set of at most $d$ vertices of $R$. Extend it, if necessary, to a $d$-element subset of $R$. Richness supplies at least $k$ common neighbours in $G$.

Embed the vertices of $B$ one at a time. At every step fewer than $k$ vertices have already been used, while at least $k$ common neighbours are available, so one unused choice remains. This greedy embedding preserves every edge of $H$ and proves