Subscribe to the weekly news from TrueShelf

## Triangles in a random graph

Let $G = G(n, \frac{1}{2})$ be a random graph on $n$ vertices, i.e., for each pair of verices $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$.

• Find $E[T_n]$, the expectation of $T_n$.

• Find $Var[T_n]$, the variance of $T_n$.

• Prove that with high probability every vertex of $G$ is incident to a triangle. In other words, let $p_n$ be the probability that for every vertex $i$, there is a triangle in $G$ containing $i$. Prove that $p_n$ tends to 1 as $n$ tends to infinity.

Source: folklore

0

0

0

0

0

0

0

0

0

0