= Solution
Embed the part $A$ injectively into the <rich set in a graph> $R$. List the vertices of $B$ as $b_1,\ldots,b_q$. When embedding $b_i$, the images of its at most $s$ neighbours in $A$ have at least $|H|$ common neighbours in $G$: extend that image set to an $s$-subset of $R$ if necessary, noting that enlarging a set can only shrink its common neighbourhood. At most $|H|-1$ vertices have already been used, so one common neighbour remains available for $b_i$. Choosing it embeds every edge incident with $b_i$ and keeps the map injective. Continuing greedily embeds $H$ in $G$. This is the <rich-set embedding lemma>.
Back to article page
