= Solution
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}.
$$
Back to article page
