Probability of triangles in $G(n, 1/2)$ I am trying to solve the following problem: Let $G = G(n, \frac{1}{2})$ be a random graph on $n$ vertices, i.e., for each pair of vertices $i, j$, we add the edge $(i, j)$ independently with probability $\frac{1}{2}$. Let $T_n$ be the number of triangles (i.e., cycles of length 3) in $G$. I am trying to find $E[T_n]$, the expectation of $T_n$, and $Var[T_n]$, the variance of $T_n$. Then, I need to find a way to prove that with high probability every vertex of $G$ is incident to a triangle (or in other words, let $p_n$ be the probability that for every vertex $i$, there is a triangle in $G$ containing $i$, and then prove that $p_n$ tends to 1 as $n$ tends to infinity.) Any help or suggestions would be appreciated! Thanks!
 A: Hint: I would start by considering a single vertex $v$. 
If we knew how many neighbors $v$ has (degree of $v$), then how many triangles does it participate in? It is a random variable, but what is its conditioned on that degree?
Of course, we do not know the degree of $v$. But again what is the degree distribution?
If we knew the expected number of triangles for a vertex $v$, then what is the expected number of triangles in the entire graph? 
A: In this answer I work more generally with $G\left(n,p\right)$ and
under the convention that $\binom{m}{k}=0$ if $k\notin\left\{ 0,\cdots,m\right\} $.
Let $S:=\left\{ s\in\wp\left\{ 1,\dots,n\right\} \mid\#s=3\right\} $
and note that $\#S=\binom{n}{3}$. 
For $s=\left\{ i,j,k\right\} \in S$ let $X_{s}$ denote the random variable that takes value $1$ if the edges $\left(i,j\right),\left(i,k\right),\left(j,k\right)$ are added
and takes value $0$ otherwise. Then $T_{n}=\sum_{s\in S}X_{s}$ so
that: $$\mathbb{E}T_{n}=\mathbb{E}\sum_{s\in S}X_{s}=\sum_{s\in S}\mathbb{E}X_{s}=\binom{n}{3}p^{3}$$
Likewise $T_{n}^{2}=\sum_{s\in S}\sum_{t\in S}X_{s}X_{t}$ so that: $$\mathbb{E}T_{n}^{2}=\sum_{s\in S}\sum_{t\in S}\mathbb{E}X_{s}X_{t}$$
and to find $\mathbb{E}X_{s}X_{t}$ we discern the following cases:


*

*$s\cap t=\varnothing$. We have $\#\left\{ \langle s,t\rangle\in S^{2}\mid s\cap t=\varnothing\right\} =\binom{n}{3}\binom{n-3}{3}$
and $\mathbb{E}X_{s}X_{t}=p^{6}$.

*$\#\left(s\cap t\right)=1$. We have $\#\left\{ \langle s,t\rangle\in S^{2}\mid\#\left(s\cap t\right)=1\right\} =\binom{n}{3}3\binom{n-3}{2}$
and $\mathbb{E}X_{s}X_{t}=p^{6}$.

*$\#\left(s\cap t\right)=2$. We have $\#\left\{ \langle s,t\rangle\in S^{2}\mid\#\left(s\cap t\right)=2\right\} =\binom{n}{3}3\binom{n-3}{1}$
and $\mathbb{E}X_{s}X_{t}=p^{5}$.

*$s=t$. We have $\#\left\{ \langle s,t\rangle\in S^{2}\mid s=t\right\} =\binom{n}{3}$
and $\mathbb{E}X_{s}X_{t}=p^{3}$.
This leads to $\mathbb{E}T_{n}^{2}=\binom{n}{3}p^{3}\left[\binom{n-3}{3}p^{3}+3\binom{n-3}{2}p^{3}+3\binom{n-3}{1}p^{2}+1\right]$
hence: $$\text{Var}T_{n}=\mathbb{E}T_{n}^{2}-\left(\mathbb{E}T_{n}\right)^{2}=\binom{n}{3}p^{3}\left[\binom{n-3}{3}p^{3}+3\binom{n-3}{2}p^{3}-\binom{n}{3}p^{3}+3\binom{n-3}{1}p^{2}+1\right]$$
Working this out we find: $$\text{Var}T_{n}=\binom{n}{3}p^{3}\left[p^{3}\left(8-3n\right)+3p^{2}\left(n-3\right)+1\right]$$
