Finding Expectation and Variance of number of “V” shape in Random Graph

Question

Q: There are n vertices where every pair of vertices is connected by an edge independently with probability p. Find the Expectation and Variance of number of "V"s shape in Random Graph given that "V" is formed by 3 vertices {i,j,k} where there are exactly 2 edges between them.

---

I first let N=number of V shape is the random graph and found that ${E[N]}$ ${=}$ ${n \choose 3}$${3(p^2)(1-p)}$.

What is the Variance of N?

Answer 1

To compute the variance of $N$, the hardest part is to compute $\mathbb E[N^2]$, since $\text{Var}[N] = \mathbb E[N^2] - \mathbb E[N]^2$. We can think of $N^2$ as counting ordered pairs of "V" shapes in the random graph. This can be split up as a sum over indicator variables $I_{\{a,b,c\},\{d,e,f\}}$ where $\{a,b,c\}$ are distinct vertices and $\{d,e,f\}$ are distinct vertices: we define $I_{\{a,b,c\},\{d,e,f\}} =1$ if $\{a,b,c\}$ and $\{d,e,f\}$ both form Vs.

The expected value of $I_{\{a,b,c\},\{d,e,f\}}$ depends on the size of the intersection $\{a,b,c\} \cap \{d,e,f\}$.

• If the intersection is empty, the probabilities are independently $3p^2(1-p)$ and the overall probability is $(3p^2(1-p))^2$. There are $\binom n3 \cdot \binom{n-3}{3}$ such cases.
• If the intersection has size $1$, still no edges are shared, and the probability is the same as in the previous case. There are $\binom n3 \cdot 3\binom{n-3}{2}$ such cases.
• If the intersection has size $2$, there are two cases. With probability $p^4(1-p)$ we form two Vs meeting along their non-edge. With probability $4p^3(1-p)^2$ instead of $p^4$, we form two Vs meeting along an edge. There are $\binom n3 \cdot \binom32(n-3)$ such cases.
• If the intersection has size $3$, then $\{a,b,c\} = \{d,e,f\}$. There are $\binom n3$ such cases with the probability $3p^2(1-p)$ that you've already found.

Combine all these, subtract $\mathbb E[N]^2 = \left(\binom n3 3p^2(1-p)\right)^2$, and you have the variance.