Past exam of the mathematics course of the University of Cambridge / 2017 / ii / Paper 3 / 15H / Solution

A graph Ramsey number $R(s,t)$ is the least $N$ such that every red-blue edge colouring of the complete graph $K_N$ has a red $K_s$ or a blue $K_t$. At a vertex in $K_{R(s-1,t)+R(s,t-1)}$, either at least $R(s-1,t)$ neighbours have red incident edges or at least $R(s,t-1)$ have blue incident edges. In the first case find a red $K_{s-1}$ and adjoin the vertex, or a blue $K_t$; the second case is symmetric. ThusStarting with $R(2,t)=t$ and $R(s,2)=s$, induction gives the binomial upper bound for a Ramsey numberFor the lower construction, partition $2t-2$ vertices into two classes of size $t-1$, colour inside-class edges red and between-class edges blue. Red cliques have at most $t-1$ vertices, and the blue graph is bipartite, so has no odd cycle.

Conversely, a graph without an odd cycle is bipartite: in each connected component colour vertices by the parity of the length of a path from a root; differing path parities would give an odd closed walk, hence an odd cycle. On $2t-1$ vertices one of the two blue bipartition classes has at least $t$ vertices. Every edge within it is red, giving a red $K_t$. Thus $2t-1$ is the exact threshold for this alternative.