= Solution
A <connected graph> with $n>1$ has no <isolated vertices>. Conversely, a disconnected <graph> with no <isolated vertices> has a <connected component> with size between $2$ and $n/2$. We must show that this latter event has <probability> tending to zero.
The permitted component-size estimate excludes sizes between $\log\log n$ and $n/2$ <with high probability>. For the remaining small sizes, let $C_k$ count components with $k$ vertices. A <connected graph> on a fixed $k$-vertex set contains a <spanning tree>. By the <Cayley formula>, there are $k^{k-2}$ labelled <trees>, as follows from the <Prüfer code> <bijection> between labelled <trees> and sequences of $k-2$ labels. A <union bound> over the <trees>, together with the absence of every <edge> to the complementary <vertex set>, gives
$$
\mathbb E C_k\leq\binom nk k^{k-2}p^{k-1}(1-p)^{k(n-k)}.
$$
Put $a=np=\log n+c$ and $L=\lceil\log\log n\rceil$. Using $\binom nk\leq(en/k)^k$ and $1-p\leq e^{-p}$, uniformly for $2\leq k\leq L$ we obtain
$$
\mathbb E C_k\leq\frac{n}{a k^2}\left(\frac{e^{1-c}a}{n}\right)^k e^{pk^2}.
$$
Here $pL^2\to0$. Therefore, with $\rho_n=e^{1-c}a/n\to0$,
$$
\sum_{k=2}^L\mathbb E C_k
\leq\frac{2n}{a}\sum_{k=2}^{\infty}\rho_n^k
=O(a/n)\longrightarrow0.
$$
The <Markov inequality> excludes all these small components <with high probability>. Together with the permitted estimate, this proves that the difference between the <probability> of connectivity and the <probability> of no <isolated vertices> tends to zero. Hence
$$
\boxed{\mathbb P(G\text{ is connected})\longrightarrow e^{-e^{-c}}.}
$$
Back to article page
