[proofplan] The lower regime follows directly from the [Isolated Vertex Threshold](/theorems/2059): an isolated vertex disconnects the graph, so if isolated vertices appear with probability tending to $1$, connectivity fails. For the upper regime, we bound the probability of a disconnection by a union bound over all "witness" cuts: if $G$ is disconnected, some set $A$ with $1 \leq |A| \leq n/2$ has no edges to its complement. We split the union bound at $k = \varepsilon n/4$: for small $k$, we use $\binom{n}{k} \leq n^k$ and $1 - p \leq e^{-p}$ to bound each summand by $n^{-3k\varepsilon/4}$; for large $k$, we use $\binom{n}{k} \leq 2^n$ and $k(n-k) \geq \varepsilon n^2/8$ to show the whole tail decays exponentially. [/proofplan]

[step:Deduce the lower regime from the isolated vertex threshold] Assume $p \leq (1-\varepsilon)\frac{\log n}{n}$. By the [Isolated Vertex Threshold](/theorems/2059), in this regime \begin{align*} \mathbb{P}(G \text{ has an isolated vertex}) \to 1 \quad \text{as } n \to \infty. \end{align*} A graph containing an isolated vertex $v$ has $\{v\}$ as a component disjoint from every other vertex, hence is disconnected whenever $n \geq 2$. Therefore \begin{align*} \{G \text{ has an isolated vertex}\} \subseteq \{G \text{ is disconnected}\}, \end{align*} so $\mathbb{P}(G \text{ is connected}) \leq \mathbb{P}(G \text{ has no isolated vertex}) \to 0$. [/step]

[step:Reduce disconnection to the existence of a small empty cut]Assume $p \geq (1+\varepsilon) \frac{\log n}{n}$. Suppose $G$ is disconnected. Then $V(G)$ partitions into components; let $C$ be any component. Set $A := C$ if $|C| \leq n/2$, otherwise $A := V(G) \setminus C$. In either case $A$ is a proper non-empty subset of $V(G)$ with $1 \leq |A| \leq \lfloor n/2 \rfloor$, and there are no edges between $A$ and $V(G) \setminus A$ (any such edge would merge $C$ with another component, contradicting $C$ being a component). Writing $e(A, V(G) \setminus A)$ for the number of edges of $G$ across the cut, \begin{align*} \{G \text{ is disconnected}\} \subseteq \bigcup_{\substack{A \subset V(G) \\ 1 \leq |A| \leq n/2}} \{e(A, V(G) \setminus A) = 0\}. \end{align*} For a fixed $A$ with $|A| = k$, the number of potential edges between $A$ and $V(G) \setminus A$ is $k(n - k)$; each is present independently with probability $p$, so \begin{align*} \mathbb{P}(e(A, V(G) \setminus A) = 0) = (1-p)^{k(n-k)}. \end{align*} By the union bound, summing over all $\binom{n}{k}$ subsets of size $k$ and all $k \in \{1, \ldots, \lfloor n/2 \rfloor\}$, \begin{align*} \mathbb{P}(G \text{ is disconnected}) \leq \sum_{k=1}^{\lfloor n/2 \rfloor} \binom{n}{k} (1-p)^{k(n-k)}. \end{align*}[/step]

[guided]A disconnected graph has at least two components. Pick any component $C$. Either $|C| \leq n/2$ or $|V(G) \setminus C| \leq n/2$ — in either case, taking $A$ to be the smaller of $C$ or its complement gives a set with $1 \leq |A| \leq n/2$. Why no edges between $A$ and $V(G) \setminus A$? If $A = C$, then by definition of component, no edges leave $C$. If $A = V(G) \setminus C$, then no edges cross from $V(G) \setminus C$ to $C$, which is the same condition. Either way, $e(A, V(G) \setminus A) = 0$. So the event $\{G \text{ is disconnected}\}$ is contained in the union, over all $A$ with $1 \leq |A| \leq n/2$, of $\{e(A, V(G) \setminus A) = 0\}$. By the union bound: \begin{align*} \mathbb{P}(G \text{ is disconnected}) \leq \sum_A \mathbb{P}(e(A, V(G) \setminus A) = 0). \end{align*} The probability of the event $\{e(A, V(G) \setminus A) = 0\}$ depends only on $k = |A|$: it's $(1-p)^{k(n-k)}$, since there are $k(n-k)$ possible cross edges and each must be absent (independently). Grouping by size gives the binomial sum above. A subtlety: we use *unordered* subsets (the cut defined by $A$ is the same as the cut defined by $V(G) \setminus A$). The restriction $|A| \leq n/2$ avoids double-counting the same cut when $|A| \neq n/2$; for $|A| = n/2$ (only if $n$ is even), each cut is counted twice, but overcounting only worsens the bound, so we accept this.[/guided]

[step:Bound the small-$k$ part of the sum via $\binom{n}{k} \leq n^k$]Split the sum at $k_0 := \lfloor \varepsilon n / 4 \rfloor$. For $k \leq k_0$, use $\binom{n}{k} \leq n^k$ and $1 - p \leq e^{-p}$: \begin{align*} \binom{n}{k}(1-p)^{k(n-k)} \leq n^k e^{-p k(n-k)} = \left(n e^{-p(n-k)}\right)^k. \end{align*} Since $k \leq \varepsilon n / 4$, we have $n - k \geq n(1 - \varepsilon/4)$, so \begin{align*} p(n-k) \geq (1+\varepsilon) \tfrac{\log n}{n} \cdot n(1 - \varepsilon/4) = (1+\varepsilon)(1 - \varepsilon/4) \log n. \end{align*} Computing $(1+\varepsilon)(1-\varepsilon/4) = 1 + \varepsilon - \varepsilon/4 - \varepsilon^2/4 = 1 + 3\varepsilon/4 - \varepsilon^2/4 \geq 1 + \varepsilon/2$ (for $\varepsilon \leq 1$, the second-order term is dominated). Therefore \begin{align*} n e^{-p(n-k)} \leq n \cdot n^{-(1 + \varepsilon/2)} = n^{-\varepsilon/2}, \end{align*} and \begin{align*} \binom{n}{k}(1-p)^{k(n-k)} \leq n^{-k\varepsilon/2}. \end{align*} Summing over $k = 1, \ldots, k_0$, \begin{align*} \sum_{k=1}^{k_0} \binom{n}{k}(1-p)^{k(n-k)} \leq \sum_{k=1}^{\infty} n^{-k\varepsilon/2} = \frac{n^{-\varepsilon/2}}{1 - n^{-\varepsilon/2}} \leq 2 n^{-\varepsilon/2} \end{align*} for $n$ large enough that $n^{-\varepsilon/2} \leq 1/2$, and this tends to $0$.[/step]

[guided]The idea: for "thin" cuts ($|A| \leq \varepsilon n/4$), we have $n - k \approx n$, so $k(n-k) \approx kn$. Each summand is \begin{align*} \binom{n}{k}(1-p)^{k(n-k)}. \end{align*} The $\binom{n}{k}$ factor is at most $n^k$ (a crude but sufficient bound). The $(1-p)^{k(n-k)}$ factor is at most $e^{-pk(n-k)}$. Multiplying: \begin{align*} n^k e^{-pk(n-k)} = \big(n \cdot e^{-p(n-k)}\big)^k. \end{align*} We aim to show this base is less than $1$, so the whole term decays geometrically in $k$. With $k \leq \varepsilon n/4$, $n - k \geq (1 - \varepsilon/4) n$. Substituting $p \geq (1+\varepsilon) \log n / n$: \begin{align*} p(n-k) \geq (1+\varepsilon)(1-\varepsilon/4) \log n. \end{align*} Expanding: $(1+\varepsilon)(1-\varepsilon/4) = 1 + 3\varepsilon/4 - \varepsilon^2/4 \geq 1 + \varepsilon/2$ for $\varepsilon \in (0, 1]$ (since $3\varepsilon/4 - \varepsilon^2/4 = \varepsilon(3 - \varepsilon)/4 \geq \varepsilon/2$ iff $3 - \varepsilon \geq 2$ iff $\varepsilon \leq 1$). Hence $n e^{-p(n-k)} \leq n \cdot n^{-(1 + \varepsilon/2)} = n^{-\varepsilon/2}$. The base of our geometric series is $n^{-\varepsilon/2}$, which tends to $0$. Summing the geometric series and bounding by its infinite version: \begin{align*} \sum_{k=1}^{k_0} n^{-k\varepsilon/2} \leq \frac{n^{-\varepsilon/2}}{1 - n^{-\varepsilon/2}} \to 0. \end{align*}[/guided]

[step:Bound the large-$k$ part of the sum via $\binom{n}{k} \leq 2^n$ and $k(n-k) \geq \varepsilon n^2/8$]For $k_0 < k \leq \lfloor n/2 \rfloor$, use $\binom{n}{k} \leq 2^n$. For $k \geq \varepsilon n / 4$ and $k \leq n/2$, we have $n - k \geq n/2$, hence $k(n-k) \geq (\varepsilon n/4)(n/2) = \varepsilon n^2 / 8$. Also $1 - p \leq e^{-p}$, so \begin{align*} \binom{n}{k}(1-p)^{k(n-k)} \leq 2^n e^{-p k(n-k)} \leq 2^n e^{-p \varepsilon n^2 / 8}. \end{align*} Substituting $p \geq (1+\varepsilon) \log n / n$, \begin{align*} p \varepsilon n^2 / 8 \geq (1+\varepsilon) \varepsilon n \log n / 8. \end{align*} The number of terms in the large-$k$ range is at most $n/2$, so \begin{align*} \sum_{k = k_0 + 1}^{\lfloor n/2 \rfloor} \binom{n}{k} (1-p)^{k(n-k)} &\leq \tfrac{n}{2} \cdot 2^n e^{-(1+\varepsilon)\varepsilon n \log n / 8} \\ &= \exp\!\left(\log(n/2) + n \log 2 - (1+\varepsilon)\varepsilon \tfrac{n \log n}{8}\right). \end{align*} The $n \log n$ term dominates $n \log 2$ and $\log(n/2)$ as $n \to \infty$, so the exponent tends to $-\infty$ and the sum tends to $0$.[/step]

[guided]For "thick" cuts ($|A| \geq \varepsilon n / 4$), both sides of the cut have size at least $\varepsilon n / 4$ and at most $n(1 - \varepsilon/4)$, so the product $k(n - k)$ is of order $n^2$. Specifically, $k \geq \varepsilon n / 4$ and $n - k \geq n/2$ give \begin{align*} k(n-k) \geq \frac{\varepsilon n}{4} \cdot \frac{n}{2} = \frac{\varepsilon n^2}{8}. \end{align*} The probability of no cross edges is thus at most $e^{-p \varepsilon n^2 / 8}$, an exponentially small quantity. The number of subsets $A$ of size $k$ in the large range is at most $2^n$ (total subsets). The number of sizes is at most $n/2$. So \begin{align*} \sum_{k = k_0 + 1}^{\lfloor n/2 \rfloor} \binom{n}{k}(1-p)^{k(n-k)} \leq \frac{n}{2} \cdot 2^n \cdot e^{-p \varepsilon n^2 / 8}. \end{align*} Taking logs: \begin{align*} \log\!\left(\frac{n}{2} \cdot 2^n e^{-p\varepsilon n^2 / 8}\right) = \log(n/2) + n \log 2 - p \varepsilon n^2 / 8. \end{align*} Using $p \geq (1+\varepsilon)\log n / n$: \begin{align*} p \varepsilon n^2 / 8 \geq (1+\varepsilon) \varepsilon n \log n / 8. \end{align*} This grows like $n \log n$, which dominates the $n \log 2$ term (linear in $n$) and the $\log(n/2)$ term (logarithmic). So the exponent tends to $-\infty$ and the entire sum vanishes. Intuition: there are at most $2^n$ bipartitions, each contributing a probability of order $e^{-p n^2}$ for the cut being empty. Since $p n^2 \gg n$, the exponential wins handily over the count.[/guided]

[step:Combine the two parts to conclude] By the union bound and the previous two steps, \begin{align*} \mathbb{P}(G \text{ is disconnected}) &\leq \sum_{k=1}^{k_0} \binom{n}{k}(1-p)^{k(n-k)} + \sum_{k=k_0+1}^{\lfloor n/2 \rfloor}\binom{n}{k}(1-p)^{k(n-k)} \\ &\to 0 + 0 = 0. \end{align*} Hence $\mathbb{P}(G \text{ is connected}) \to 1$. Together with the lower regime from the first step, this establishes the claimed dichotomy and completes the proof. [/step]