Past exam of the mathematics course of the University of Cambridge / 2010 / ii / Paper 1 / 17F / a / Solution

The diagonal diagonal Ramsey number $R(s)$ is the least $n$ such that every red-blue edge coloring of $K_n$ contains a monochromatic $K_s$. More generally let $R(s,t)$ require a red $K_s$ or blue $K_t$. The base cases are $R(1,t)=R(s,1)=1$. Given $R(s-1,t)+R(s,t-1)$ vertices, select one vertex. Either it has at least $R(s-1,t)$ red neighbors or at least $R(s,t-1)$ blue neighbors. Applying the corresponding smaller problem and, when needed, adjoining that selected vertex givesInduction and Pascal's identity now prove existence and