Past exam of the graph Theory and Probabilistic Combinatorics course of the University of Oxford / 2008 / A / 3 / d / Solution

Assume the usual nontrivial case $\chi (G)\ge 2$ and $|H|\ge 2$. On $(\chi (G)-1)(|H|-1)$ vertices partition into $\chi (G)-1$ equal classes of size $|H|-1$. Color all edges between distinct classes red and all edges within a class blue. The red graph is $(\chi (G)-1)$-colorable, so it contains no copy of $G$. Every blue connected component has only $|H|-1$ vertices, so connectedness prevents a blue copy of $H$. Therefore one more vertex is necessary:If $G$ is edgeless or $H$ has one vertex, the displayed lower bound is just one and holds directly.