variance of number of isolated vertices in random graph $G(n,p)$ Suppose we have random graph $G(n,p)$ from a uniform distribution with $n$ vertices and independently, each edge present with probability $p$. Calculating it's expected number of isolated vertices proves quite easy, chance of single vertex to be isolated is equal to $(1-p)^{n-1}$, then using linearity of probability, expected number of isolated vertices is equal to $n\times(1-p)^{n-1}$. However, I am tasked to calculate the variance of this number, or at least decent approximation of it, without any idea how to proceed.

Let $P_{n,k}$ be the probability of exactly $k$ isolated vertices in $G(n,p)$.  Look at what happens when we add a new vertex gives:
$$
P_{n+1,k}=q^n P_{n,k-1} + (1-q^{n-k})q^k P_{n,k} + \sum_{i=1}^{n-k}\binom{k+i}{i}p^iq^kP_{n,k+i}
$$
where


*

*$q=1-p$ as usual

*the first term is the new vertex being isolated

*the second term is new vertex not isolated but there are $k$ isolated vertices we started off from $G(n,p)$ (so there is an edge from vertex $n+1$ to one of the $n-k$ vertices which gives the $1-q^{n-k}$ factor, and $n+1$ cannot join to any of the $k$ isolated vertices in $[n]$ so the other factor $q^k$

*the sum is for starting with a graph of $k+i$ isolated vertices and this new vertex is neighbour to exactly $i$ of these.


Using this recurrence, you can show the probability generating function of the number of isolated vertices
$$
G_n(z):=\sum_{k=0}^n P_{n,k}z^k
$$
satisfies
$$
G_n(z)=q^{n-1}(z-1)G_{n-1}(z)+G_{n-1}(1+q(z-1)).
$$
This has closed form solution
$$
G_n(z)=\sum_{k=0}^n\binom{n}{k}q^{nk-\binom{k}{2}}(z-1)^k
$$
and so you obtain
$$
\operatorname{Var}[\#\text{isolated vertices}]=nq^{n-1}((1-q^{n-1})+(n-1)pq^{n-2}).
$$
