# Graphs: Expected Number of Triangles and Variance

Gold Member

## Homework Statement

Let $G$ be a random graph on $n$ vertices:
1) What is the expected number of triangles in $G$?
2) What is the variance in the number of triangles?

N/A

## The Attempt at a Solution

I think I can do (1) by using indicator variables. In particular, let $X$ denote the number of triangles in $G$, suppose $\theta_{ijk}$ is the indicator variable that the triple of vertices $i,j,k$ make a triangle, and let $A_{ijk}$ denote the event that the triple of vertices make a triangle. Then, we know
$$E(X) = \sum_{i,j,k}P(A_{ijk})$$
where the sum extends over all triples $i,j,k$. Since there are $\binom{n}{3}$ such triples and since $P(A_{ijk}) = \frac{1}{8}$, this means
$$E(X) = \binom{n}{3}\frac{1}{8}$$
which gives us the expected number of triangles.

Now, I just need help getting started with the variance problem. I think I'm just supposed to utilize the fact that $Var(X) = E(X^2) - E(X)^2$, but I'm not sure. Any help is appreciated.