= Connectivity of a fixed-density binomial random graph
{title2=$\Pr(G(n,p)\text{ connected})\to1,\quad 0<p<1\text{ fixed}$}
A disconnected <binomial random graph> has a <connected component of a graph> with at most half its <vertices>. The <union bound> over its possible <vertex sets> gives
$$
\Pr(G(n,p)\text{ disconnected})
\leq\sum_{s=1}^{\lfloor n/2\rfloor}\binom ns(1-p)^{s(n-s)}
\leq\sum_{s=1}^{\lfloor n/2\rfloor}\bigl(n(1-p)^{n/2}\bigr)^s.
$$
The final <geometric series> bound tends to zero for fixed $p>0$.
Back to article page
