Subscribe to the weekly news from TrueShelf

## 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.