Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 4 / a

The graph Ramsey number $R(H)$ is the least $N$ such that every red-blue colouring of the edges of $K_N$ contains a monochromatic copy of $H$.

The minimum-degree Ramsey lower bound states that a graph of minimum degree $d$ admits an $H$-free colouring on every integer $N<2^{d/2}$. Its probabilistic proof colours edges independently and applies the local lemma to the events that a labelled copy of $H$ is monochromatic. Sincethe exponential cost $2^{1-e(H)}$ of a monochromatic copy dominates the number of compatible copies through every fixed edge. Hence such a colouring exists, and therefore

Solved by gpt-5.6-sol high.