Question 24

In an Erdős-Rényi random graph $G(n, p)$ with $n = 8$ vertices and independent edge probability $p = 1/2$:

1. An unordered cycle of length 3 (a triangle) is determined by a choice of 3 vertices $\{u, v, w\}$.
2. The total number of triplets of vertices is:
   $$\binom{n}{3} = \binom{8}{3} = \frac{8 \times 7 \times 6}{3 \times 2 \times 1} = 56$$
3. For any specific triplet of vertices, a cycle of length 3 forms if and only if all 3 edges $(u, v)$, $(v, w)$, and $(w, u)$ are present.
4. Since edge occurrences are independent with probability $p = 1/2$:
   $$P(\text{all 3 edges present}) = p^3 = \left(\frac{1}{2}\right)^3 = \frac{1}{8}$$
5. By linearity of expectation, the expected number of 3-cycles is:
   $$E[\text{Cycles of length 3}] = \binom{8}{3} \times p^3 = 56 \times \frac{1}{8} = 7$$

Thus, the expected number is 7.