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

Let $Y$ be the number of isolated vertices and set $\lambda =e^{-c}$. For fixed $k\ge 1$, the falling factorial $(Y{)}_k$ counts ordered $k$-tuples of distinct isolated vertices. A specified tuple is isolated exactly when all edges incident to its vertices are absent. There are $k(n-k)+\left(\genfrac{}{}{0ex}{}{k}{2}\right)$ such edges, soSince $np=\log n+c$ and $n{p}^2=o(1)$, taking logarithms givesThus every fixed factorial moment tends to ${\lambda }^k$. We use the standard factorial-moment criterion for Poisson convergence: nonnegative integer-valued random variables whose factorial moments converge, for every fixed order, to ${\lambda }^k$ converge in distribution to $\mathrm{Poisson}(\lambda )$. Consequently $Y$ has that limiting distribution, and its mass at each fixed integer converges. In particular,This establishes the limiting probability of at least one isolated vertex, rather than merely a bound based on its expectation.

The factorial-moment argument above gives $Y\Rightarrow \mathrm{Poisson}(\lambda )$ with $\lambda =e^{-c}$. Because $Y$ is integer-valued, apply convergence in distribution at the continuity points $3/2$ and $5/2$ and subtract. This proves

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

For the unheaded degree-one continuation, write $X={\sum }_{v=1}^n{I}_v$, where $I_v$ indicates that vertex $v$ has degree one. Withwe haveFor distinct vertices $u,v$, separate the cases where their connecting edge is present or absent. If it is present, all their other incident edges must be absent. If it is absent, each vertex chooses its unique neighbour among the other $n-2$ vertices; those two neighbours may coincide. The respective edge constraints are independent even in that case. ThusDividing by $q^2$ gives the exact ratioThe first term tends to zero because $(n-1{)}^{2}p$ has order $n\log n$; the second tends to one. Consequently its variance satisfiesThe Chebyshev inequality now yields $\mathbb{P}(X=0)\le \mathrm{Var}X/(\mathbb{E}X{)}^2\to 0$. A vertex of degree one exists with high probability, even though the limiting probability of having an isolated vertex is strictly between zero and one.