Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 17J / a

Ramsey theorem follows from $R(s,t)\le R(s-1,t)+R(s,t-1)$: at a vertex, either at least $R(s-1,t)$ neighbours or at least $R(s,t-1)$ non-neighbours produce the desired clique or independent set. Induction with $R(2,t)=R(s,2)=t$ gives $R(s,t)\le \left(\genfrac{}{}{0ex}{}{s+t-2}{s-1}\right)$, hence $R(t)\le \left(\genfrac{}{}{0ex}{}{2t-2}{t-1}\right)<2^{2t}$.