= Solution
Write $q=1-p$. A disconnected <graph> has a <connected component of a graph> of size $1\leq s\leq\lfloor n/2\rfloor$. For a fixed $s$-element <vertex set> $S$, all $s(n-s)$ <edges> between $S$ and its complement must be absent. Their independent absence has probability $q^{s(n-s)}$. The <union bound> gives
$$
\mathbb P(G(n,p)\text{ disconnected})
\leq\sum_{s=1}^{\lfloor n/2\rfloor}\binom ns q^{s(n-s)}
\leq\boxed{\sum_{s=1}^{\lfloor n/2\rfloor}
\left(nq^{n/2}\right)^s}.
$$
Set $r_n=nq^{n/2}$. Since $p$ is fixed in $(0,1)$, $r_n\to0$. For large $n$, the final sum is at most the <geometric series> $r_n/(1-r_n)$, which tends to zero. Hence the <binomial random graph> is <connected> with probability tending to one, as in <connectivity of a fixed-density binomial random graph>.
Back to article page
