= 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) gives
$$
\operatorname{Var}(X)
=\binom n3p^3(1-p^3)
+3\binom n3(n-3)p^5(1-p).
$$
With $\mu=\binom n3p^3$, the <triangle variance in a binomial random graph> therefore satisfies
$$
\frac{\operatorname{Var}(X)}{\mu^2}
\leq\frac1{\binom n3p^3}
+\frac{3(n-3)}{\binom n3p}
=O((np)^{-3})+O((n^2p)^{-1}).
$$
Both terms tend to zero when $np\to\infty$, because $n^2p=n(np)\to\infty$. Applying part (ii) proves
$$
\boxed{\mathbb P(X>0)\longrightarrow1},
$$
completing the <triangle-existence threshold in a binomial random graph>.
Back to article page
