Random Isolated Vertex

Consider a graph consisting of $n$ vertices in which each possible edge is included with probability $p = p(n)$ (a probability that explicitly depends on the size of the graph). This construction provides a probabilistic framework, as described by Gilbert [1], to study typical properties of graphs as $n$ increases.

Denote this graph by $G(n, p)$, and consider $p(n) = \frac{1}{\sqrt{n}}$. What is the probability of finding an isolated vertex (i.e., a vertex with no neighbours) in $G(n, p)$ as $n$ increases?

Hint: Consider that the probability of finding an isolated vertex in a random graph with $n$ vertices is $P_\mathrm{isolated}(n) = (1-p)^{n-1}$.

a) It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{n}$, converging to 1.

b) It increases with $n$, approaching $P_\mathrm{isolated}(n) = 1 - \frac{1}{\sqrt{n}}$, converging to 1.

c) It decreases with $n$, approaching $P_\mathrm{isolated}(n) = \frac{\log n}{n}$, converging to 0.

d) It decreases with $n$, approaching $P_\mathrm{isolated}(n) = \exp(-\sqrt{n})$, converging to 0.

e) None of the above

[1] Gilbert, E. N. (1959). Random graphs. The Annals of Mathematical Statistics, 30(4), 1141-1144.

Original idea: Daniel Gardin