= Solution
<Chebyshev inequality> states that, for a random variable $Y$ of finite <variance> and any $a>0$,
$$
\mathbb P(|Y-\mathbb EY|\geq a)
\leq\frac{\operatorname{var}Y}{a^2}.
$$
Let $X=\sum_T I_T$ count <triangles in a graph>[triangles], where $T$ ranges over the three-element vertex sets and $I_T$ is the corresponding <indicator random variable>. Then
$$
\mu=\mathbb EX=\binom n3p^3.
$$
Two distinct triangle indicators are independent unless their triangles share an edge. There are
$$
\binom n2\binom{n-2}2
$$
unordered pairs sharing an edge, and each covariance is
$$
p^5-p^6\leq p^5.
$$
Therefore
$$
\operatorname{var}X
\leq\binom n3p^3
+2\binom n2\binom{n-2}2p^5.
$$
It follows that
$$
\frac{\operatorname{var}X}{\mu^2}
=O\left(\frac1{n^3p^3}+\frac1{n^2p}\right)
\longrightarrow0
$$
when $np\to\infty$. Chebyshev's inequality now gives
$$
\mathbb P(X=0)
\leq\mathbb P(|X-\mu|\geq\mu)
\leq\frac{\operatorname{var}X}{\mu^2}
\longrightarrow0.
$$
Hence
$$
\boxed{\mathbb P(E_3)\longrightarrow1},
$$
as summarized by the <triangle count in a binomial random graph>.
Back to article page
