Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 36 / 3 / b / iii / Solution

Two distinct triangles in a graph with at most one common vertex use disjoint edges, so their indicator random variables are independent and have zero covariance. A pair sharing an edge has covariance $p^5-p^6$. The count from part (i) givesWith $\mu =\left(\genfrac{}{}{0ex}{}{n}{3}\right)p^3$, the triangle variance in a binomial random graph therefore satisfiesBoth terms tend to zero when $np\to \infty$, because $n^{2}p=n(np)\to \infty$. Applying part (ii) provescompleting the triangle-existence threshold in a binomial random graph.