[proofplan] Let $I$ be the number of isolated vertices in $G \sim G(n,p)$. We analyse the two regimes separately. In the upper regime $p \geq (1+\varepsilon)\frac{\log n}{n}$, we show $\mathbb{E}[I] \to 0$ using the inequality $1-p \leq e^{-p}$, then conclude by the first moment method (Markov's inequality). In the lower regime $p \leq (1-\varepsilon)\frac{\log n}{n}$, we show $\mathbb{E}[I] \to \infty$ via the estimate $\log(1-p) \geq -p(1 + \varepsilon/4)$, then apply the second moment method after computing $\operatorname{Var}(I)$ from the shared-edge covariance between pairs of isolated-vertex indicators. [/proofplan] [step:Set up the isolated-vertex count as a sum of indicators] For each vertex $v \in V(G)$, let \begin{align*} X_v: \Omega &\to \{0, 1\} \\ \omega &\mapsto \mathbb{1}_{\{\deg(v) = 0\}}(\omega), \end{align*} so that $I := \sum_{v \in V(G)} X_v$ counts the isolated vertices. Since vertex $v$ is isolated iff all $n-1$ potential edges incident to $v$ are absent, and edges are independent with probability $p$, \begin{align*} \mathbb{P}(X_v = 1) = (1-p)^{n-1}, \end{align*} and by linearity of expectation \begin{align*} \mathbb{E}[I] = n(1-p)^{n-1}. \end{align*} [/step] [step:Show $\mathbb{E}[I] \to 0$ in the upper regime via $1-p \leq e^{-p}$] Assume $p \geq (1+\varepsilon)\frac{\log n}{n}$. We use the standard inequality $1 - x \leq e^{-x}$ valid for all $x \in \mathbb{R}$, applied to $x = p$: \begin{align*} \mathbb{E}[I] = n(1-p)^{n-1} \leq n e^{-p(n-1)}. \end{align*} For $n \geq 2$ we have $n - 1 \geq n/2$, so \begin{align*} \mathbb{E}[I] \leq n e^{-pn/2} \leq n \exp\!\left(-\tfrac{1+\varepsilon}{2} \log n\right) = n^{1 - (1+\varepsilon)/2} = n^{(1-\varepsilon)/2}. \end{align*} This bound is not tight enough. We sharpen by using $n - 1 \geq n(1 - 1/n)$ and noting that for any $\delta > 0$ and $n$ large enough $n - 1 \geq n/(1+\delta)$. Taking $\delta = \varepsilon/2$, for all $n$ sufficiently large $n-1 \geq n/(1+\varepsilon/2)$, hence \begin{align*} \mathbb{E}[I] \leq n e^{-p(n-1)} \leq n \exp\!\left(-\tfrac{1+\varepsilon}{1 + \varepsilon/2} \log n\right) = n^{1 - (1+\varepsilon)/(1+\varepsilon/2)}. \end{align*} Since $(1+\varepsilon)/(1+\varepsilon/2) = 1 + \varepsilon/(2+\varepsilon) > 1$, the exponent is strictly negative, so $\mathbb{E}[I] \to 0$ as $n \to \infty$. [guided] Our goal in this regime is to show that isolated vertices disappear. The first moment method is the natural tool: if $\mathbb{E}[I] \to 0$, then $\mathbb{P}(I \geq 1) \to 0$ by Markov. The obstacle is that $(1-p)^{n-1}$ is a product we need to estimate from above. The standard trick is $1 - x \leq e^{-x}$, valid because the function $f(x) = e^{-x} - (1-x)$ satisfies $f(0) = 0$ and $f'(x) = 1 - e^{-x} \geq 0$ for $x \geq 0$. Applying this with $x = p$: \begin{align*} \mathbb{E}[I] = n(1-p)^{n-1} \leq n e^{-p(n-1)}. \end{align*} Now we substitute the hypothesis $p \geq (1+\varepsilon) \log n / n$. The issue is the $n-1$ exponent rather than $n$: we need $p(n-1)$ to be slightly more than $\log n$. For $n$ sufficiently large, $n - 1 \geq n/(1+\varepsilon/2)$ (equivalently, $1 - 1/n \geq 1/(1+\varepsilon/2)$, which holds for $n$ large since the LHS $\to 1$ and the RHS $< 1$). Therefore \begin{align*} p(n-1) \geq (1+\varepsilon)\frac{\log n}{n} \cdot \frac{n}{1+\varepsilon/2} = \frac{1+\varepsilon}{1+\varepsilon/2}\, \log n. \end{align*} Write $\alpha := (1+\varepsilon)/(1+\varepsilon/2) = 1 + \varepsilon/(2+\varepsilon) > 1$. Then \begin{align*} \mathbb{E}[I] \leq n e^{-p(n-1)} \leq n \cdot n^{-\alpha} = n^{1 - \alpha} \to 0, \end{align*} since $1 - \alpha < 0$. By Markov's inequality, \begin{align*} \mathbb{P}(I \geq 1) \leq \mathbb{E}[I] \to 0, \end{align*} which is exactly the statement that $G$ has no isolated vertex with probability tending to $1$. [/guided] [/step] [step:Show $\mathbb{E}[I] \to \infty$ in the lower regime via $\log(1-p) \geq -p(1 + \varepsilon/4)$] Assume $p \leq (1-\varepsilon)\frac{\log n}{n}$; in particular, $p \to 0$ as $n \to \infty$. The Taylor expansion of $\log(1-x)$ about $x = 0$ is \begin{align*} \log(1-x) = -x - \frac{x^2}{2} - \frac{x^3}{3} - \cdots = -x - \sum_{k=2}^\infty \frac{x^k}{k}. \end{align*} For $x \in [0, 1/2]$ we have $\sum_{k=2}^\infty x^k/k \leq x^2 \sum_{k=0}^\infty (1/2)^k = 2x^2$, hence $\log(1-x) \geq -x - 2x^2$ for $x \in [0, 1/2]$. Since $p \to 0$, for $n$ large enough $p \leq \varepsilon/8$, and then $2p \leq \varepsilon/4$, giving \begin{align*} \log(1-p) \geq -p - 2p^2 = -p(1 + 2p) \geq -p\!\left(1 + \tfrac{\varepsilon}{4}\right). \end{align*} Exponentiating and raising to the $(n-1)$-th power: \begin{align*} (1-p)^{n-1} \geq \exp\!\left(-p(1 + \varepsilon/4)(n-1)\right) \geq \exp\!\left(-(1 + \varepsilon/4)(1 - \varepsilon) \log n\right), \end{align*} where in the last step we used $p(n-1) \leq pn \leq (1-\varepsilon) \log n$. Therefore \begin{align*} \mathbb{E}[I] = n(1-p)^{n-1} \geq n \cdot n^{-(1-\varepsilon)(1 + \varepsilon/4)} = n^{1 - (1-\varepsilon)(1+\varepsilon/4)}. \end{align*} Expanding: $(1-\varepsilon)(1+\varepsilon/4) = 1 + \varepsilon/4 - \varepsilon - \varepsilon^2/4 = 1 - 3\varepsilon/4 - \varepsilon^2/4$, so \begin{align*} \mathbb{E}[I] \geq n^{3\varepsilon/4 + \varepsilon^2/4} \to \infty. \end{align*} [guided] Here we want to bound $(1-p)^{n-1}$ from *below*, which is the opposite direction from the upper regime. The inequality $1-p \leq e^{-p}$ gives an upper bound on $(1-p)^{n-1}$, so we need the reverse. The natural tool is to use the second-order Taylor expansion of $\log(1-p)$: \begin{align*} \log(1-p) = -p - \frac{p^2}{2} - \frac{p^3}{3} - \cdots. \end{align*} All correction terms are negative, so $\log(1-p) \leq -p$ (this is equivalent to $1-p \leq e^{-p}$, the inequality we used before). To get a lower bound, we need to bound the tail. For $0 \leq p \leq 1/2$: \begin{align*} \sum_{k=2}^\infty \frac{p^k}{k} \leq \sum_{k=2}^\infty p^k = \frac{p^2}{1-p} \leq 2p^2, \end{align*} so $\log(1-p) \geq -p - 2p^2$. Since $p \to 0$ in our regime, for $n$ sufficiently large we have $2p \leq \varepsilon/4$, so $-p - 2p^2 \geq -p(1 + \varepsilon/4)$. Exponentiating, \begin{align*} 1-p \geq e^{-p(1+\varepsilon/4)}. \end{align*} Raising to the $(n-1)$-th power and using $p(n-1) \leq pn \leq (1-\varepsilon)\log n$: \begin{align*} (1-p)^{n-1} \geq e^{-(1+\varepsilon/4)p(n-1)} \geq e^{-(1+\varepsilon/4)(1-\varepsilon)\log n} = n^{-(1+\varepsilon/4)(1-\varepsilon)}. \end{align*} Multiplying by $n$: \begin{align*} \mathbb{E}[I] \geq n^{1 - (1+\varepsilon/4)(1-\varepsilon)}. \end{align*} Expanding the product $(1+\varepsilon/4)(1-\varepsilon) = 1 - 3\varepsilon/4 - \varepsilon^2/4$, so the exponent is $3\varepsilon/4 + \varepsilon^2/4 > 0$. Hence $\mathbb{E}[I] \to \infty$. Observation: why did we need the second-order term at all? The first-order approximation $(1-p)^{n-1} \approx e^{-p(n-1)}$ is not enough in this delicate regime — a factor of $1 + o(1)$ in the exponent shifts the exponent of $n$ by a constant factor, and we need the resulting exponent to be *strictly positive*. Keeping track of the $(1 + \varepsilon/4)$ factor ensures this. [/guided] [/step] [step:Compute $\operatorname{Var}(I)$ via the shared-edge covariance] We cannot conclude $\mathbb{P}(I = 0) \to 0$ from $\mathbb{E}[I] \to \infty$ alone — Markov's inequality goes the wrong way. We apply the second moment method. Write \begin{align*} \operatorname{Var}(I) = \sum_{u, v \in V(G)} \operatorname{Cov}(X_u, X_v) = \sum_{u} \operatorname{Var}(X_u) + \sum_{u \neq v} \operatorname{Cov}(X_u, X_v). \end{align*} Since each $X_u \in \{0,1\}$ is a Bernoulli indicator, $\operatorname{Var}(X_u) \leq \mathbb{E}[X_u]$, so the diagonal contributes at most $\mathbb{E}[I]$. For the off-diagonal terms with $u \neq v$, note that $\{X_u = 1\} \cap \{X_v = 1\}$ means both $u$ and $v$ are isolated. This requires the absence of $2(n-1) - 1 = 2n - 3$ potential edges: each vertex has $n-1$ incident edges, but the edge $uv$ is counted twice. Since distinct edges are independent, \begin{align*} \mathbb{P}(X_u = 1, X_v = 1) = (1-p)^{2n-3}. \end{align*} On the other hand, $\mathbb{P}(X_u = 1) \mathbb{P}(X_v = 1) = (1-p)^{2n-2}$. Therefore \begin{align*} \operatorname{Cov}(X_u, X_v) &= (1-p)^{2n-3} - (1-p)^{2n-2} \\ &= (1-p)^{2n-3}\left(1 - (1-p)\right) = p(1-p)^{2n-3}. \end{align*} Summing over the $n(n-1)$ ordered pairs $u \neq v$ and combining with the diagonal bound, \begin{align*} \operatorname{Var}(I) \leq \mathbb{E}[I] + n(n-1) \cdot p(1-p)^{2n-3}. \end{align*} [guided] The standard second moment approach expands \begin{align*} \operatorname{Var}(I) = \mathbb{E}[I^2] - \mathbb{E}[I]^2 = \sum_u \operatorname{Var}(X_u) + \sum_{u \neq v} \operatorname{Cov}(X_u, X_v). \end{align*} The diagonal terms are easy: for a Bernoulli $X_u$ with mean $q_u$, $\operatorname{Var}(X_u) = q_u(1 - q_u) \leq q_u$, so $\sum_u \operatorname{Var}(X_u) \leq \mathbb{E}[I]$. The off-diagonal terms are the interesting part. For $u \neq v$, we need $\mathbb{P}(X_u = 1, X_v = 1)$, the probability that *both* $u$ and $v$ are isolated. This is the probability that *no* edge touches $u$ or $v$. How many edges can touch $u$ or $v$? Vertex $u$ has $n-1$ potential incident edges; vertex $v$ has $n-1$ potential incident edges. But the edge $uv$ is incident to both, so by inclusion-exclusion, the total number of distinct edges incident to $u$ *or* $v$ is $(n-1) + (n-1) - 1 = 2n-3$. Since these edges are independent, \begin{align*} \mathbb{P}(X_u = 1, X_v = 1) = (1-p)^{2n-3}. \end{align*} Compare with the product of marginals: \begin{align*} \mathbb{P}(X_u = 1)\mathbb{P}(X_v = 1) = (1-p)^{n-1} \cdot (1-p)^{n-1} = (1-p)^{2n-2}. \end{align*} The indicators are *positively correlated* — the shared edge $uv$ is "double-counted" in the product of marginals, so the joint probability is $(1-p)^{-1}$ times the product. The covariance is \begin{align*} \operatorname{Cov}(X_u, X_v) = (1-p)^{2n-3} - (1-p)^{2n-2} = (1-p)^{2n-3} \cdot p. \end{align*} Summing over the $n(n-1)$ ordered pairs and combining: \begin{align*} \operatorname{Var}(I) \leq \mathbb{E}[I] + n(n-1) p (1-p)^{2n-3}. \end{align*} [/guided] [/step] [step:Apply the second moment method to conclude $\mathbb{P}(I = 0) \to 0$] Chebyshev's inequality (or the [second moment method](/theorems/???)) gives \begin{align*} \mathbb{P}(I = 0) \leq \mathbb{P}\!\left(|I - \mathbb{E}[I]| \geq \mathbb{E}[I]\right) \leq \frac{\operatorname{Var}(I)}{(\mathbb{E}[I])^2}. \end{align*} We bound the right-hand side. First, \begin{align*} \frac{\mathbb{E}[I]}{(\mathbb{E}[I])^2} = \frac{1}{\mathbb{E}[I]} \to 0 \end{align*} by the previous step. Second, using $(\mathbb{E}[I])^2 = n^2 (1-p)^{2n-2}$, \begin{align*} \frac{n(n-1) p (1-p)^{2n-3}}{n^2 (1-p)^{2n-2}} = \frac{n(n-1)}{n^2} \cdot \frac{p}{1-p} \leq \frac{p}{1-p}. \end{align*} Since $p \leq (1-\varepsilon)\frac{\log n}{n} \to 0$, we have $p/(1-p) \to 0$. Combining, \begin{align*} \frac{\operatorname{Var}(I)}{(\mathbb{E}[I])^2} \leq \frac{1}{\mathbb{E}[I]} + \frac{p}{1-p} \to 0 + 0 = 0, \end{align*} so $\mathbb{P}(I = 0) \to 0$, i.e., $\mathbb{P}(G \text{ has an isolated vertex}) = \mathbb{P}(I \geq 1) \to 1$. [guided] The second moment method rests on Chebyshev's inequality. If $\mathbb{E}[I] > 0$, then $\{I = 0\} \subseteq \{|I - \mathbb{E}[I]| \geq \mathbb{E}[I]\}$, so by Chebyshev, \begin{align*} \mathbb{P}(I = 0) \leq \frac{\operatorname{Var}(I)}{(\mathbb{E}[I])^2}. \end{align*} The strategy is thus to show $\operatorname{Var}(I) = o((\mathbb{E}[I])^2)$ — the variance is much smaller than the squared mean. Using the variance bound from the previous step: \begin{align*} \frac{\operatorname{Var}(I)}{(\mathbb{E}[I])^2} \leq \frac{\mathbb{E}[I]}{(\mathbb{E}[I])^2} + \frac{n(n-1)p(1-p)^{2n-3}}{n^2 (1-p)^{2n-2}}. \end{align*} The first term equals $1/\mathbb{E}[I]$, which tends to $0$ because $\mathbb{E}[I] \to \infty$. The second term simplifies using the identity $(1-p)^{2n-3} / (1-p)^{2n-2} = 1/(1-p)$: \begin{align*} \frac{n(n-1)p}{n^2 (1-p)} = \frac{n-1}{n} \cdot \frac{p}{1-p} \leq \frac{p}{1-p}. \end{align*} Since $p \to 0$, this term tends to $0$. Both terms vanish, so $\operatorname{Var}(I)/(\mathbb{E}[I])^2 \to 0$, and Chebyshev delivers $\mathbb{P}(I = 0) \to 0$. Combining the two regimes: in the upper regime $\mathbb{P}(G \text{ has isolated vertex}) \to 0$, and in the lower regime $\mathbb{P}(G \text{ has isolated vertex}) \to 1$, which is precisely the statement of the theorem. [/guided] [/step]