Square of the expectation of number of edges not in a triangle in random graph The following question is from page 27 in the book Graphical Evolution, An introduction to Theory of Random Graphs by Edgar M. Palmer. I feel that my argument is correct (who doesn't?), but the answer is needed for the next question which doesn't work out, so I thought I'd start by ascertaining that this part is correct.

Question: Let $X(G)$ be the number of edges of a random graph $G=G(n,p)$ that are not in triangles. Find $\mathbb{E}(X^2)$.

My attempt: Label the edges $e_1,\dots e_{{n \choose 2}}$. Let $A_i$ be the event that $e_i$ is not in a triangle, and let $X_i$ be the indicator random variable for the event $A_i$.
First, the probability that the edge $e_i$ is not in a triangle is $$\mathbb{P}[A_i]=(1-p^3)^{n-2}$$ since each the edge $e_i$ can be part of $n-2$ different triangles.
Second, the expectation for the number of edges not in triangles is $$\mathbb{E}[X]=\sum_i \mathbb{E}[X_i]=\sum_i \mathbb{P}[A_i]={n \choose 2}(1-p^3)^{n-2}.$$
Third, for the expectation of $X^2$, we have $$\mathbb{E}[X^2]=\mathbb{E}[X]+\sum_{i\neq j}\mathbb{E}[X_iX_j].$$
The sum is equal to $${n \choose 2}\sum_j \mathbb{E}[X_1X_j]={n \choose 2}\sum_j \mathbb{P}[A_1 \cap A_j].$$ Here I attempted to split the sum into two cases depending on whether $A_1$ and $A_j$ are dependent or independent. They are dependent if the edges $e_1$ and $e_j$ share a vertex and can form a triangle together.


  ${}$

In case (A), there is one way to form a triangle with both $e_1$ and $e_j$, and $(n-3)+(n-3)$ ways to form triangles with either $e_1$ or $e_j$ (without them being in the same triangle). By independence this gives a probability of $$\mathbb{P}[A_1A_j]=(1-p^3)^{2n-7}.$$ There are $2(n-2)$ ways for case (A) to occur, since each of the other $n-2$ vertices may be connected to $e_1$ in $2$ ways.
In case (B), we simply have $$\mathbb{P}[A_1A_j]=\mathbb{P}[A_1]\mathbb{P}[A_j]=(1-p^3)^{2n-4}.$$
There are ${n-2 \choose 2}$ ways for case (B) to occur.
Adding all this together we find that $$\mathbb{E}[X^2]={n \choose 2}\left[(1-p^3)^{n-2}+2(n-2)(1-p^3)^{2n-7}+{n-2 \choose 2}(1-p^3)^{2n-4}\right].$$
Is it correct thus far? After this I suspect I need to do some asymptotic analysis on this expression, but I'm not sure it's correct in the first place.
 A: I am only beginning to read your answer, but there is already a few errors:


*

*Nitpick, but the title is wrong. You are trying to compute the expectation of the square, not the square of the expectation.

*More annoying, what follows is wrong:

First, the probability that the edge $e_i$ is not in a triangle is $$\mathbb{P}[A_i]=(1-p^3)^{n-2}$$ since each the edge $e_i$ can be part of $n-2$ different triangles.

There are $n-1$ distinct events. First, the edge $e_i$ must belong to the graph. In addition, for each of the $n-2$ couples of edges which form a triangle with $e_i$, at least one of these edges does not belong to the graph. As all these events are independent, this makes:
$$\mathbb{P}[A_i]=p(1-p^2)^{n-2}.$$
Your error is twofold: first, you mistook the event "the edge $e_i$ exists and does not belong to a triangle" with the event "there is not triangle with the edge $e_i$". Second, you misapplied the independence in the computation of the probability of the second event (the $n-2$ events you were taking into account are not independent, as they all depend on the state of the edge $e_i$).
The same mistake is reapeated in the remainder of the proof. For this kind of exercise, you should always do a quick sanity check. At fixed $n \ge 3$, you would expect the random graph $G(n, 0)$ to be totally disconnected, and the random graph $G(n, 1)$ to be complete, so if you plug $p = 0$ or $p=1$ in your final formula you should find $0$.
