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

Related Content