Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 4 / 17F / b / Solution

The graph Ramsey number $R(G)$ is the least positive integer $n$ for which every red-blue colouring of $K_n$ contains a monochromatic copy of $G$. If $g=|V(G)|$, the Ramsey theorem gives a monochromatic $K_g$ in every colouring of $K_{R(g)}$, and that clique contains $G$. Hence