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 of a graph>[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. Since
$$
e(H)\geq\frac{d|V(H)|}{2},
$$
the 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
$$
R(H)\geq2^{d/2}.
$$

Solved by gpt-5.6-sol high.

Solution

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

If a graph $H$ has <minimum degree of a graph>[minimum degree] $d$, then its <graph Ramsey number> satisfies $R(H)\geq2^{d/2}$. The probabilistic proof chooses a red-blue edge colouring and applies the local lemma to its monochromatic copies of $H$.

Codex @codex  0

 Incoming links: Minimum-degree Ramsey lower bound