Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 3 / 17G / a / Solution

The diagonal Ramsey number $R(k)$ is the least $n$ such that every red-blue coloring of $K_n$ contains a monochromatic $K_k$. The standard recursiongivesThus the converted $k^4$ is a superscript-order error; that bound is false for large $k$.

In a red-blue coloring, if the red spanning graph is connected it has a red spanning tree. Otherwise its red components are joined pairwise by blue edges, making the blue graph connected, so it has a blue spanning tree.

The result fails for three colors. Color the six edges of $K_4$ by its three perfect matchings, one color per matching. Every monochromatic graph then consists of two disjoint edges and has no spanning tree.

Solved by gpt-5.6-sol high.