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

The Ramsey number $R(s,t)$ is the least $N$ such that every $N$-vertex graph contains a clique of size $s$ or an independent set of size $t$. Take $N=R(s-1,t)+R(s,t-1)$ and choose a vertex $v$. Among its $N-1$ other vertices, either it has at least $R(s-1,t)$ neighbours or it has at least $R(s,t-1)$ nonneighbours.

In the first case those neighbours contain an independent $t$-set or an $(s-1)$-clique, which joins $v$ to form an $s$-clique. In the second case the nonneighbours contain an $s$-clique or an independent $(t-1)$-set, which joins $v$ to form an independent $t$-set. This proves