= 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. With
$$
q=\mathbb P(I_v=1)=(n-1)p(1-p)^{n-2},
$$
we have
$$
\mathbb E X=nq\sim e^{-c}(\log n+c)\longrightarrow\infty.
$$
For 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. Thus
$$
\mathbb E(I_uI_v)=p(1-p)^{2n-4}+(n-2)^2p^2(1-p)^{2n-5}.
$$
Dividing by $q^2$ gives the exact ratio
$$
R_n=\frac{1}{(n-1)^2p}+\left(\frac{n-2}{n-1}\right)^2\frac{1}{1-p}\longrightarrow1.
$$
The first term tends to zero because $(n-1)^2p$ has order $n\log n$; the second tends to one. Consequently its <variance> satisfies
$$
\frac{\operatorname{Var}X}{(\mathbb EX)^2}
=\frac{1}{nq}+\left(1-\frac1n\right)R_n-1\longrightarrow0.
$$
The <Chebyshev inequality> now yields $\mathbb P(X=0)\leq\operatorname{Var}X/(\mathbb EX)^2\to0$. \b[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.
Back to article page
