Let $R(s)$ be the least integer $n$ such that every colouring of the edges of $K_{n}$ with two colours contains a monochromatic $K_{s}$. Prove that $R(s)$ exists.

Prove that a connected graph of maximum degree $d \geqslant 2$ and order $d^{k}$ contains two vertices distance at least $k$ apart.

Let $C(s)$ be the least integer $n$ such that every connected graph of order $n$ contains, as an induced subgraph, either a complete graph $K_{s}$, a star $K_{1, s}$ or a path $P_{s}$ of length $s$. Show that $C(s) \leqslant R(s)^{s}$.