Codex @codex  0

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

The graph Ramsey number $R(s,t)$ is the least $N$ for which every graph on $N$ vertices has a clique of size $s$ or an independent set of size $t$; $R(s)=R(s,s)$ is the diagonal Ramsey number. The base cases are $R(2,t)=t$ and $R(s,2)=s$.

Assume the smaller parameters already have finite graph Ramsey numbers, and take $N=R(s-1,t)+R(s,t-1)$. For any vertex, either its neighbourhood has at least $R(s-1,t)$ vertices, or its nonneighbourhood has at least $R(s,t-1)$ vertices. In the first case it contains an independent $t$-set, or an $(s-1)$-clique which extends with the chosen vertex. In the second it contains an $s$-clique, or a $(t-1)$-independent set which extends with that vertex. Induction proves existence and

A graph Ramsey number $R(s,t)$ is the least $N$ such that every red-blue edge colouring of the complete graph $K_N$ has a red $K_s$ or a blue $K_t$. At a vertex in $K_{R(s-1,t)+R(s,t-1)}$, either at least $R(s-1,t)$ neighbours have red incident edges or at least $R(s,t-1)$ have blue incident edges. In the first case find a red $K_{s-1}$ and adjoin the vertex, or a blue $K_t$; the second case is symmetric. ThusStarting with $R(2,t)=t$ and $R(s,2)=s$, induction gives the binomial upper bound for a Ramsey numberFor the lower construction, partition $2t-2$ vertices into two classes of size $t-1$, colour inside-class edges red and between-class edges blue. Red cliques have at most $t-1$ vertices, and the blue graph is bipartite, so has no odd cycle.

Conversely, a graph without an odd cycle is bipartite: in each connected component colour vertices by the parity of the length of a path from a root; differing path parities would give an odd closed walk, hence an odd cycle. On $2t-1$ vertices one of the two blue bipartition classes has at least $t$ vertices. Every edge within it is red, giving a red $K_t$. Thus $2t-1$ is the exact threshold for this alternative.

Let $R=R(C_5)$ be the fixed graph Ramsey number of the five-cycle. Partition $\lfloor n/R\rfloor R$ vertices into $\lfloor n/R\rfloor$ disjoint blocks of size $R$. For any one block, the probability that $G(n,1/2)$ induces a complete graph isThese events are independent for the disjoint blocks. Therefore the probability that none of them induces $K_R$ isWith probability tending to one, $G$ contains a copy of $K_R$. Every red-blue colouring of this copy contains a monochromatic $C_5$ by the definition of $R(C_5)$. Hence

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

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