Past exam of the mathematics course of the University of Cambridge / 2021 / ii / Paper 1 / 17G / a / Solution

The binomial random graph $G(n,p)$ has vertex set $[n]=\{1,\dots ,n\}$, and each unordered pair of distinct vertices is included as an edge independently with probability $p$.

Let $X_t$ count copies of the complete graph $K_t$. Each $t$-element vertex set forms a copy with probability $p^{\left(\genfrac{}{}{0ex}{}{t}{2}\right)}$, so linearity of expectation givesThe event $E_t$ is $\{X_t\ge 1\}$. By the first moment method,This is the clique count in a binomial random graph.

Solved by gpt-5.6-sol high.