Past exam of the mathematics course of the University of Cambridge / 2006 / iii / Paper 14 / 4 / c

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, givesPut $a=np=\log n+c$ and $L=\lceil \log \log n\rceil$. Using $\left(\genfrac{}{}{0ex}{}{n}{k}\right)\le (en/k{)}^k$ and $1-p\le e^{-p}$, uniformly for $2\le k\le L$ we obtainHere $p{L}^2\to 0$. Therefore, with ${\rho }_n=e^{1-c}a/n\to 0$,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