Past exam of the mathematics course of the University of Cambridge / 2024 / iii / Paper 132 / 4 / c / Solution

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