Subscribe to the weekly news from TrueShelf

0

Basics of Random Graphs

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}\).

  • Show that \(G\) is almost surely connected when \(n\) is large.

Related Content