= Solution
Let $I_{ij}$ be the <indicator random variable> that the unordered <vertex> pair $\{i,j\}$ has no <common neighbour>. For each of the other $n-2$ <vertices>, the two required <edges> are both present with probability $p^2$. The edge pairs for different candidate neighbours are disjoint sets of independent random choices. Thus $\mathbb E I_{ij}=(1-p^2)^{n-2}$. <Linearity of expectation> yields
$$
\boxed{\mathbb E X=\binom n2(1-p^2)^{n-2}},
$$
the <missing common-neighbour count in a binomial random graph>.
Back to article page
