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 decr...