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

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.