Isolated Vertices at the Connectivity Window

The Isolated-Vertex Count in the Connectivity Window

For a graph to be connected, every vertex must be joined to every other vertex by a path. An isolated vertex, which has degree zero, immediately prevents this when the graph has at least two vertices. Near the connectivity threshold, isolated vertices do not simply disappear: their count has a nontrivial limiting distribution.

All graphs in this tutorial are finite and simple. In the random graph $G(n,p)$, the vertex set is $\{1,\dots,n\}$, and each possible edge is included independently with probability $p$. We fix a real constant $c$ and take $p=(\log n+c)/n$. For every fixed $c$, this is a valid probability for all sufficiently large $n$: then $0<\log n+c<n$. Write $X_n$ for the number of isolated vertices.

Definition: A vertex is isolated if its degree is zero. The random variable $X_n$ counts the isolated vertices of $G(n,p)$. A Poisson random variable of mean $\lambda>0$ takes value $j$ with probability $e^{-\lambda}\lambda^j/j!$, for each integer $j\ge 0$.

The key calculation is the probability that a specified group of vertices are all isolated. This gives more information than the expected value of $X_n$, because it records how the isolation events overlap.

Joint Isolation Probabilities and Factorial Moments

For a nonnegative integer $x$ and integer $k\ge1$, write $(x)_k=x(x-1)\cdots(x-k+1)$, and set $(x)_0=1$. The quantity $(X_n)_k$ counts ordered lists of $k$ distinct isolated vertices.

Lemma: For $0\le k\le n$, $$ \mathbb{E}\big[(X_n)_k\big]=(n)_k(1-p)^{kn-k(k+1)/2}. $$

Proof. For $k=0$, both sides equal $1$. Now let $1\le k\le n$, and fix an ordered list of $k$ distinct vertices. For all of them to be isolated, every edge with at least one endpoint in the list must be absent. There are $k(n-k)$ edges from the list to the other vertices and $\binom{k}{2}$ edges within the list. The total is $k(n-k)+\binom{k}{2}=kn-k(k+1)/2$. By independence, the probability all these edges are absent is $(1-p)^{kn-k(k+1)/2}$. There are $(n)_k$ ordered lists. Summing their indicator variables gives the formula. $\square$

For each fixed $k$, substitute $p=(\log n+c)/n$. The exponent $A=kn-k(k+1)/2$ satisfies $Ap=k(\log n+c)+o(1)$, since $k$ is fixed. Also $Ap^2=o(1)$. Using $\log(1-p)=-p+O(p^2)$ therefore gives $A\log(1-p)=-k(\log n+c)+o(1)$. Finally, $(n)_k/n^k\to1$. Together these estimates yield the limit below.

Theorem: For each fixed integer $k\ge0$, when $p=(\log n+c)/n$, $$ \mathbb{E}\big[(X_n)_k\big]\longrightarrow e^{-kc}. $$ In particular, the limiting factorial moments are those of a Poisson random variable of mean $e^{-c}$.

Proof. For $k=0$, both the factorial moment and $e^{-kc}$ equal $1$. For fixed $k\ge1$, the lemma and the estimates just established give $$ \mathbb{E}\big[(X_n)_k\big] =(n)_k\exp\big(-k(\log n+c)+o(1)\big). $$ Since $(n)_k=n^k(1+o(1))$, the right-hand side is $n^ke^{-k\log n-kc}(1+o(1))=e^{-kc}(1+o(1))$. This proves the stated limit. If $Z$ is Poisson with mean $\lambda=e^{-c}$, its factorial moment of order $k$ is $\mathbb{E}[(Z)_k]=\lambda^k=e^{-kc}$: substituting its probabilities gives the sum $e^{-\lambda}\sum_{j=k}^\infty (j)_k\lambda^j/j!=\lambda^k$. $\square$

Worked Example: The Centre of the Window

Set $c=0$, so $p=(\log n)/n$ for sufficiently large $n$. For $k=1$, the exact formula gives $$ \mathbb{E}[X_n]=n(1-p)^{n-1}. $$

Here $(n-1)p=(n-1)\log n/n=\log n-(\log n)/n$, while $np^2=(\log n)^2/n\to0$. Thus $(n-1)\log(1-p)=-\log n+o(1)$, and $\mathbb{E}[X_n]=n\exp(-\log n+o(1))\to1$. For every fixed $k$, the theorem gives $\mathbb{E}[(X_n)_k]\to e^0=1$. These are the factorial moments of a Poisson random variable of mean $1$.

Check: The predicted probability of no isolated vertices is $e^{-1}$, and the predicted probability of exactly one is $e^{-1}\cdot1^1/1!=e^{-1}$. These values are consequences of the limiting distribution, not of the expectation alone.

Worked Example: A Positive Shift

Take $c=\log 2$. Then $e^{-c}=e^{-\log 2}=1/2$. The limiting mean number of isolated vertices is therefore $1/2$, and the limiting probability of no isolated vertices is $e^{-1/2}$.

For example, the limiting probability of exactly two isolated vertices is $$ e^{-1/2}\frac{(1/2)^2}{2!}=\frac{e^{-1/2}}{8}. $$ The corresponding limiting factorial moments are $e^{-k\log 2}=2^{-k}$ for each fixed $k$. In particular, the first is $1/2$, and the second is $1/4$.

Check: The probabilities for zero, one and two isolated vertices sum to $e^{-1/2}(1+1/2+1/8)=13e^{-1/2}/8$, which is less than $1$; the remaining probability belongs to counts of at least three. No finite partial sum is being treated as the whole distribution.

Worked Example: A Negative Shift

Take $c=-\log 3$. Then $p=(\log n-\log 3)/n$, which is positive for $n>3$, and the limiting mean is $e^{-c}=3$. The limiting probability of no isolated vertices is $e^{-3}$, and the probability of exactly one is $3e^{-3}$.

The first two limiting factorial moments are $3$ and $9$. Indeed, the theorem gives $e^{-c}=e^{\log 3}=3$ for $k=1$, and $e^{-2c}=e^{2\log 3}=9$ for $k=2$. For a Poisson variable $Z$ of mean $3$, these are $\mathbb{E}[Z]=3$ and $\mathbb{E}[Z(Z-1)]=9$.

Check: The limiting probability of exactly two isolated vertices is $e^{-3}3^2/2!=9e^{-3}/2$. The chance of seeing at least one isolated vertex tends to $1-e^{-3}$, which is larger than in the positive-shift example.

Why Factorial Moments Give the Distribution

Convergence of all fixed factorial moments is useful only if it justifies a distributional conclusion. Here that conclusion can be proved directly by finite inclusion-exclusion bounds, so no unproved moment-determinacy claim is needed.

Distributional conclusion: For every integer $j\ge0$, $$ \mathbb{P}(X_n=j)\longrightarrow e^{-\lambda}\frac{\lambda^j}{j!}, \qquad \lambda=e^{-c}. $$ Thus $X_n$ converges in distribution to a Poisson random variable of mean $e^{-c}$.

Proof. Fix $j\ge0$. For a nonnegative integer $x$, the expression $\binom{x}{j}\sum_{r=0}^R(-1)^r\binom{x-j}{r}$ is taken as zero when $x<j$. If $x=j$, it equals $1$. If $x>j$, put $y=x-j\ge1$. When $R<y$, the partial alternating sum is $(-1)^R\binom{y-1}{R}$; when $R\ge y$, it is zero. Hence for even $R$ the expression is at least the indicator of $x=j$, and for odd $R$ it is at most that indicator.

Apply these pointwise bounds to $x=X_n$ and take expectations. The identity $\binom{x}{j}\binom{x-j}{r}=(x)_{j+r}/(j!r!)$ gives, for odd $R$ and even $S$, $$ \sum_{r=0}^{R}(-1)^r\frac{\mathbb{E}[(X_n)_{j+r}]}{j!r!} \le \mathbb{P}(X_n=j) \le \sum_{r=0}^{S}(-1)^r\frac{\mathbb{E}[(X_n)_{j+r}]}{j!r!}. $$ For fixed truncation indices, take $n\to\infty$ and use the factorial-moment limits. The two bounds become partial sums of $\frac{\lambda^j}{j!}\sum_{r\ge0}(-1)^r\lambda^r/r!$. As the odd and even truncation indices tend to infinity, both partial sums converge to $\lambda^je^{-\lambda}/j!$, by the exponential series. The lower and upper bounds therefore squeeze $\mathbb{P}(X_n=j)$ to this value. These point probabilities imply convergence in distribution: for any real number that is not an integer, the probability of being below it is a finite sum of point probabilities, and these sums converge to the corresponding Poisson probability. $\square$

What This Says About Connectivity

A graph is connected if every pair of vertices is joined by a path. For $n\ge2$, a connected graph has no isolated vertex: an isolated vertex cannot have a path to any other vertex. Consequently, for the random graph in this window, $$ \mathbb{P}\big(G(n,p)\text{ is connected}\big)\le \mathbb{P}(X_n=0)\longrightarrow e^{-e^{-c}}. $$ Equivalently, the probability that there is at least one isolated vertex tends to $1-e^{-e^{-c}}$; each such graph is disconnected. This gives a precise obstruction to connectivity at the threshold scale. It is an upper bound on the limiting connectivity probability, not by itself a proof that having no isolated vertices is sufficient for connectivity.

For fixed $c$, the limiting obstruction probability is positive. Increasing $c$ decreases the limiting mean $e^{-c}$ and increases the upper bound $e^{-e^{-c}}$. For example, at $c=0$ the bound is $e^{-1}$, while at $c=\log 2$ it is $e^{-1/2}$. These are bounds arising from isolated vertices; other disconnected components would also prevent connectivity.

Common Pitfall: An Expectation Is Not a Distribution

At $c=0$, the calculation $\mathbb{E}[X_n]\to1$ does not, by itself, show that $X_n$ approaches a Poisson variable or that $\mathbb{P}(X_n=0)\to e^{-1}$. Many different random variables can have the same mean: a variable that always equals $1$ has mean $1$, but its probability of being zero is $0$, not $e^{-1}$. The correction is to calculate the joint isolation probabilities and establish the limits of every fixed factorial moment; the inclusion-exclusion argument then proves the point probabilities.

Check Your Understanding

Use the fixed-$c$ regime $p=(\log n+c)/n$, with $n$ sufficiently large that $0<p<1$.

For a specified set of three vertices, how many distinct edges must be absent for all three to be isolated?
Use the factorial-moment formula to find the limit of $\mathbb{E}[X_n(X_n-1)]$ in terms of $c$.
At $c=\log 4$, what is the limiting mean number of isolated vertices, and what is the limiting probability that there are none?
Explain why convergence of $\mathbb{E}[X_n]$ alone cannot establish the limiting probability that $X_n=0$.
State the connectivity bound supplied by the isolated-vertex limit, and explain why it is an upper bound rather than an equality established here.