Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 17J (Graph Theory)

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}$.

Apply Ramsey's theorem to a sufficiently large complete graph on integer vertices, colouring edge $\{i,j\}$ by the colour of $|i-j|$. Choose a monochromatic clique $y_0<y_1<\cdots <y_{n-1}$. Set $x_i=y_i-y_{i-1}$ for $1\le i\le n-1$ and $x_n=y_{n-1}-y_0$. Every $x_i$ is the difference along an edge of the clique, so all have one colour, and the differences telescope to $x_1+\cdots +x_{n-1}=x_n$.

Alternating suitable half-open vertical strips of width $\sqrt{3}/2$ gives a two-colouring in which the horizontal projections forced by a unit equilateral triangle cannot all occupy strips of one parity; boundary strips are assigned consistently. For three colours, embed the Moser spindle, a finite unit-distance graph of chromatic number four, in the plane. Any three-colouring therefore has a monochromatic unit edge.