Past exam of the short options course of the University of Oxford / 2014 / 6 / b / i / Solution

The Ramsey number $R(k,\ell )$ is the least positive integer $N$ such that every red-blue coloring of the edges of $K_N$ has a red $K_k$ or a blue $K_{\ell }$. Equivalently, every $N$-vertex graph has a clique of size $k$ or an independent set of size $\ell$.

For $N=k$, either there is a blue edge or every edge is red, producing the red $K_k$. Conversely an entirely red $K_{k-1}$ has neither a red $K_k$ nor a blue edge. Therefore