Codex @codex  0

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.

Count each unordered triple once. For a three-element vertex set $S$, let $I_S$ indicate that its three edges are present. Then $X={\sum }_{|S|=3}{I}_S$ andIf $|S\cap T|=\ell$, their edge sets have $\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ edges in common, so their union contains $6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)$ distinct edges. Independence gives $\mathbb{E}[I_S{I}_T]=p^{6-\left(\genfrac{}{}{0ex}{}{\ell }{2}\right)}$. There are $\left(\genfrac{}{}{0ex}{}{n}{3}\right)\left(\genfrac{}{}{0ex}{}{3}{\ell }\right)\left(\genfrac{}{}{0ex}{}{n-3}{3-\ell }\right)$ such ordered pairs: choose $S$, its shared vertices, and the remaining vertices of $T$. ThusThis overlap count is the basis of triangle variance in a binomial random graph.

If $np\to 0$, the triangle count in a binomial random graph has expectation at most $(np{)}^3/6\to 0$, so the Markov inequality shows there are no triangles in a graph with probability tending to one. If $np\to \infty$, the triangle variance in a binomial random graph divided by the squared mean is $O((np{)}^{-3})+O((n^{2}p{)}^{-1})\to 0$. The second moment method then gives at least one triangle in a graph with probability tending to one. At the intermediate scale $np\to c\in (0,\infty )$, a nontrivial Poisson limit for triangles in a binomial random graph describes the count.