Random Graph. Probability and Expectation

Question

Let $G_n$ be a random graph with $n$ vertices $\{1, 2,..., n\}$ where very pair of vertices is connected by an edge independently with probability $p ∈ (0,1)$. Given $\{i, j, k, l\}$ are a set of distinct vertices. I know there are there are $\binom{n}{2}$ possible edges and $\{i,j\}, \{i,k\},\{i,l\}, \{j,k\}, \{j,l\}$ and $\{k,l\}$ are edges in $G_n$. Using linearity of expectation, the expected number of triangle is $\binom{n}{2} p^3$. The set of 4 vertices $\{i, j, k, l\}$ is said to form a square if there are exactly 4 edges among them, forming a square. How do I find the expected number of squares in $G_n$? Is it simply $\binom{n}{2}p^4$?

Answer 1

The nC2 should be nC4. You can again use linearity of expectation, but the probability of four given vertices forming a square is not $p^4$. You need to consider the probability that there are exactly four edges among them forming a square. This is a bit more work, can you figure it out?

PS $p^4$ is the probability of four given pairs of vertices having edges. Instead, being a square is not about four given pairs having edges. There are multiple possibilities (the square could be ijkl or jikl for example) and you need to take into account that there are no more edges between the vertices than four.