[proofplan] Let $X$ count the triangles in $G \sim G(n, p)$. For $p \ll 1/n$ we use the first moment: $\mathbb{E}[X] = \binom{n}{3}p^3 \to 0$, so Markov forces $\mathbb{P}(K_3 \subseteq G) \to 0$. For $p \gg 1/n$ we use the [second moment method](/theorems/2057): we compute $\operatorname{Var}(X)$ by splitting the covariance sum over triangle pairs according to how many edges they share — pairs sharing no edges are independent, pairs sharing two edges are identical, so only the diagonal and the one-shared-edge pairs contribute. A direct estimate shows $\operatorname{Var}(X)/(\mathbb{E}[X])^2 \to 0$, and hence $\mathbb{P}(X = 0) \to 0$. [/proofplan] [step:Define the triangle-counting random variable] Let $(\Omega, \mathcal{F}, \mathbb{P})$ be a probability space carrying the independent Bernoulli($p$) edge indicators $\mathbb{1}_{\{ij \in E(G)\}}$ for $1 \leq i < j \leq n$ that define $G \sim G(n, p)$. For a triple $T = \{a, b, c\} \in \binom{[n]}{3}$, write $\{T \subseteq G\}$ for the event that all three edges $ab, ac, bc$ are present in $G$. Define \begin{align*} X : \Omega &\to \mathbb{N}_0 \\ \omega &\mapsto \sum_{T \in \binom{[n]}{3}} \mathbb{1}_{\{T \subseteq G(\omega)\}}. \end{align*} The event $\{K_3 \subseteq G\}$ coincides with $\{X \geq 1\}$. Since each triangle-event $\{T \subseteq G\}$ is the intersection of three independent Bernoulli($p$) events, $\mathbb{P}(T \subseteq G) = p^3$, and [linearity of expectation](/theorems/???) gives \begin{align*} \mathbb{E}[X] = \binom{n}{3} p^3. \end{align*} [/step] [step:Subcritical case $p \ll 1/n$: first moment and Markov] Assume $p = p(n)$ satisfies $np \to 0$ as $n \to \infty$. Then \begin{align*} \mathbb{E}[X] = \binom{n}{3} p^3 \leq \frac{n^3 p^3}{6} = \frac{(np)^3}{6} \to 0. \end{align*} Since $X$ takes values in $\mathbb{N}_0$, the event $\{X \geq 1\}$ satisfies $\mathbb{1}_{\{X \geq 1\}} \leq X$ pointwise. Taking expectations ([Markov's inequality](/theorems/???) applied to the non-negative integer-valued variable $X$ with threshold $1$), \begin{align*} \mathbb{P}(K_3 \subseteq G) = \mathbb{P}(X \geq 1) \leq \mathbb{E}[X] \to 0. \end{align*} [guided] In the subcritical regime we need to show the probability of containing a triangle vanishes. The first moment method handles this: if the expected count of triangles vanishes, the probability of having at least one triangle vanishes too. We assume $p \ll 1/n$, meaning $np = np(n) \to 0$. Bounding the binomial coefficient $\binom{n}{3} \leq n^3/6$ (the ratio $n(n-1)(n-2)/n^3$ is at most $1$), \begin{align*} \mathbb{E}[X] = \binom{n}{3} p^3 \leq \frac{n^3 p^3}{6} = \frac{(np)^3}{6}, \end{align*} and $(np)^3 \to 0$ by assumption, so $\mathbb{E}[X] \to 0$. To extract $\mathbb{P}(X \geq 1) \to 0$, we use [Markov's inequality](/theorems/???) in its integer-valued form: for a non-negative integer-valued random variable $X$, the indicator $\mathbb{1}_{\{X \geq 1\}}$ is pointwise bounded by $X$ itself (both equal 0 when $X = 0$, and $\mathbb{1}_{\{X \geq 1\}} = 1 \leq X$ when $X \geq 1$). Taking expectations, \begin{align*} \mathbb{P}(X \geq 1) = \mathbb{E}[\mathbb{1}_{\{X \geq 1\}}] \leq \mathbb{E}[X] \to 0. \end{align*} Since $\{K_3 \subseteq G\} = \{X \geq 1\}$, we conclude $\mathbb{P}(K_3 \subseteq G) \to 0$. [/guided] [/step] [step:Supercritical case $p \gg 1/n$: set up the second moment method] Assume $p = p(n)$ satisfies $np \to \infty$ as $n \to \infty$. We will show $\operatorname{Var}(X)/(\mathbb{E}[X])^2 \to 0$ and then invoke the [second moment method](/theorems/2057), which states that for a non-negative integer random variable $X$, \begin{align*} \mathbb{P}(X = 0) \leq \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2}. \end{align*} This will give $\mathbb{P}(K_3 \subseteq G) = \mathbb{P}(X \geq 1) = 1 - \mathbb{P}(X = 0) \to 1$. We first record a lower bound on $\mathbb{E}[X]$. For $n \geq 4$, \begin{align*} \binom{n}{3} = \frac{n(n-1)(n-2)}{6} \geq \frac{(n-3)^3}{6}, \end{align*} so \begin{align*} \mathbb{E}[X] = \binom{n}{3} p^3 \geq \frac{(n-3)^3 p^3}{6} \geq \frac{n^3 p^3}{48} \quad \text{for } n \geq 6, \end{align*} where in the last step we used $n - 3 \geq n/2$ for $n \geq 6$. In particular $\mathbb{E}[X] \to \infty$, since $n^3 p^3 = (np)^3 \to \infty$. [guided] For the supercritical regime, the first moment alone is insufficient — knowing $\mathbb{E}[X]$ is large does not prevent $X$ from taking the value $0$ with high probability (it could be $0$ most of the time and occasionally huge). What we need is concentration: showing that the fluctuations of $X$ are small relative to its mean. This is precisely what [the second moment method](/theorems/2057) provides: \begin{align*} \mathbb{P}(X = 0) \leq \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2}, \end{align*} valid for any non-negative integer-valued $X$. If we can show the right-hand side vanishes, we will have $\mathbb{P}(X = 0) \to 0$ and hence $\mathbb{P}(K_3 \subseteq G) \to 1$. Since this ratio has $(\mathbb{E}[X])^2$ in the denominator, we want to know that $\mathbb{E}[X]$ grows. For $n \geq 6$, we have $n - 3 \geq n/2$, so \begin{align*} \binom{n}{3} = \frac{n(n-1)(n-2)}{6} \geq \frac{(n-3)^3}{6} \geq \frac{n^3}{48}, \end{align*} and therefore $\mathbb{E}[X] \geq n^3 p^3 / 48 = (np)^3 / 48$. Since $np \to \infty$ by assumption, $\mathbb{E}[X] \to \infty$, and hence $(\mathbb{E}[X])^2 \gtrsim n^6 p^6$. The challenge now is to bound $\operatorname{Var}(X)$. [/guided] [/step] [step:Decompose $\operatorname{Var}(X)$ by the number of shared edges between triangle pairs] Expand the variance: \begin{align*} \operatorname{Var}(X) = \sum_{T, T' \in \binom{[n]}{3}} \operatorname{Cov}\left(\mathbb{1}_{\{T \subseteq G\}}, \mathbb{1}_{\{T' \subseteq G\}}\right). \end{align*} Classify each ordered pair $(T, T')$ by $k := |E(T) \cap E(T')|$, the number of edges shared. There are four cases for $T, T' \in \binom{[n]}{3}$: - $k = 0$: $T$ and $T'$ share no edge. Then $\{T \subseteq G\}$ and $\{T' \subseteq G\}$ depend on disjoint sets of edge indicators and are therefore independent, so the covariance is zero. - $k = 1$: $T$ and $T'$ share exactly one edge. Then $|V(T) \cup V(T')| = 4$ and $|E(T) \cup E(T')| = 5$. - $k = 2$: impossible. Two triangles sharing two edges share the endpoints of those edges, which are the three vertices of a triangle — so the triangles coincide, contradicting $k = 2$. - $k = 3$: $T = T'$ (the diagonal). Hence \begin{align*} \operatorname{Var}(X) = \underbrace{\sum_{T} \operatorname{Var}(\mathbb{1}_{\{T \subseteq G\}})}_{\text{diagonal}} + \underbrace{\sum_{\substack{T \neq T' \\ |E(T) \cap E(T')| = 1}} \operatorname{Cov}(\mathbb{1}_{\{T \subseteq G\}}, \mathbb{1}_{\{T' \subseteq G\}})}_{\text{one shared edge}}. \end{align*} [claim:Diagonal contribution] \begin{align*} \sum_{T} \operatorname{Var}(\mathbb{1}_{\{T \subseteq G\}}) \leq \mathbb{E}[X]. \end{align*} [proof] For each $T$, $\mathbb{1}_{\{T \subseteq G\}}$ is Bernoulli($p^3$), so \begin{align*} \operatorname{Var}(\mathbb{1}_{\{T \subseteq G\}}) = p^3(1 - p^3) \leq p^3 = \mathbb{E}[\mathbb{1}_{\{T \subseteq G\}}]. \end{align*} Summing over $T \in \binom{[n]}{3}$ gives $\mathbb{E}[X]$. [/proof] [/claim] [claim:One-shared-edge contribution] \begin{align*} \sum_{\substack{T \neq T' \\ |E(T) \cap E(T')| = 1}} \operatorname{Cov}(\mathbb{1}_{\{T \subseteq G\}}, \mathbb{1}_{\{T' \subseteq G\}}) \leq 3 n^4 p^5. \end{align*} [proof] The number of ordered pairs $(T, T')$ with $T \neq T'$ and $|E(T) \cap E(T')| = 1$ is at most $\binom{n}{3} \cdot 3(n - 3)$: choose $T$ in $\binom{n}{3}$ ways, then one of $T$'s three edges to share in $3$ ways, then a fourth vertex to complete $T'$ in $(n-3)$ ways. Hence the count is at most $\binom{n}{3} \cdot 3(n-3) \leq \tfrac{n^3}{6} \cdot 3n = \tfrac{n^4}{2}$, and we use the looser bound $3 n^4$ (valid for $n \geq 1$) below to simplify. Actually we bound the count more carefully: $\binom{n}{3} \cdot 3(n-3) \leq \frac{n^3}{6} \cdot 3n = \frac{n^4}{2}$. For each such pair, the union $E(T) \cup E(T')$ has exactly $5$ edges (three from $T$, three from $T'$, minus the shared one). The event $\{T \subseteq G\} \cap \{T' \subseteq G\}$ is the event that all $5$ edges in the union are present, which has probability $p^5$ by independence of distinct edge indicators. Therefore \begin{align*} \operatorname{Cov}(\mathbb{1}_{\{T \subseteq G\}}, \mathbb{1}_{\{T' \subseteq G\}}) \leq \mathbb{E}[\mathbb{1}_{\{T \subseteq G\}} \mathbb{1}_{\{T' \subseteq G\}}] = p^5. \end{align*} Summing, \begin{align*} \sum_{\substack{T \neq T' \\ |E \cap E'| = 1}} \operatorname{Cov}(\cdots) \leq \frac{n^4}{2} \cdot p^5 \leq 3 n^4 p^5. \end{align*} [/proof] [/claim] Combining the two claims, \begin{align*} \operatorname{Var}(X) \leq \mathbb{E}[X] + 3 n^4 p^5. \end{align*} [guided] We now tackle the variance. Expanding, \begin{align*} \operatorname{Var}(X) = \operatorname{Var}\left(\sum_T \mathbb{1}_{\{T \subseteq G\}}\right) = \sum_{T, T'} \operatorname{Cov}(\mathbb{1}_{\{T \subseteq G\}}, \mathbb{1}_{\{T' \subseteq G\}}). \end{align*} The crucial observation is that the covariance vanishes whenever $T$ and $T'$ share no edge: the indicator $\mathbb{1}_{\{T \subseteq G\}}$ depends only on the three edges of $T$, and likewise for $T'$. If $E(T) \cap E(T') = \varnothing$, these are disjoint sets of independent edge indicators, so the indicators are independent and the covariance is zero. This reduces the sum to pairs sharing at least one edge. Classifying by $k = |E(T) \cap E(T')|$: - $k = 3$ (the diagonal $T = T'$): each term is $\operatorname{Var}(\mathbb{1}_{\{T \subseteq G\}}) = p^3(1 - p^3) \leq p^3$. Summing over $\binom{n}{3}$ triples gives at most $\binom{n}{3} p^3 = \mathbb{E}[X]$. - $k = 2$: two triangles sharing two edges share two edges — say $ab, ac$. But these two edges use three vertices $a, b, c$, and the third edge of each triangle must connect two of $\{a,b,c\}$ — the only remaining option is $bc$. So both triangles are $\{a, b, c\}$ and hence $T = T'$, contradicting $k = 2$. So this case is empty. - $k = 1$: $T$ and $T'$ share exactly one edge. Let us count such ordered pairs: choose $T$ in $\binom{n}{3}$ ways; choose which of the three edges of $T$ is shared ($3$ ways); the shared edge fixes two vertices of $T'$, and the third vertex of $T'$ is any of the remaining $n - 3$ vertices (not equal to the apex of $T$, since that would give $T = T'$). This yields at most $\binom{n}{3} \cdot 3(n-3) \leq \tfrac{n^4}{2}$ ordered pairs. Each pair has $|E(T) \cup E(T')| = 5$ distinct edges (the shared one plus two more from each triangle), so the probability both triangles are present is $p^5$. Each covariance is bounded by the second moment $p^5$. Total: at most $\tfrac{1}{2}n^4 p^5 \leq 3n^4 p^5$. Adding the contributions, \begin{align*} \operatorname{Var}(X) \leq \mathbb{E}[X] + 3n^4 p^5. \end{align*} [/guided] [/step] [step:Bound the variance-to-mean-squared ratio and conclude] Using $\mathbb{E}[X] \geq n^3 p^3 / 48$ for $n \geq 6$, we have $(\mathbb{E}[X])^2 \geq n^6 p^6 / 2304$. Combining with the variance bound, \begin{align*} \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2} \leq \frac{\mathbb{E}[X] + 3 n^4 p^5}{(\mathbb{E}[X])^2} = \frac{1}{\mathbb{E}[X]} + \frac{3 n^4 p^5}{(\mathbb{E}[X])^2} \leq \frac{1}{\mathbb{E}[X]} + \frac{3 n^4 p^5 \cdot 2304}{n^6 p^6} = \frac{1}{\mathbb{E}[X]} + \frac{6912}{n^2 p}. \end{align*} Since $np \to \infty$ we have $n^2 p = n \cdot (np) \to \infty$, so the second term tends to $0$. Since $\mathbb{E}[X] \geq (np)^3/48 \to \infty$, the first term tends to $0$. Hence \begin{align*} \lim_{n \to \infty} \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2} = 0. \end{align*} By the [second moment method](/theorems/2057) applied to $X$, $\mathbb{P}(X = 0) \leq \operatorname{Var}(X)/(\mathbb{E}[X])^2 \to 0$, so \begin{align*} \mathbb{P}(K_3 \subseteq G) = \mathbb{P}(X \geq 1) = 1 - \mathbb{P}(X = 0) \to 1. \end{align*} Combining with Step 2, we conclude \begin{align*} \lim_{n \to \infty} \mathbb{P}(K_3 \subseteq G) = \begin{cases} 0 & \text{if } p \ll 1/n, \\ 1 & \text{if } p \gg 1/n, \end{cases} \end{align*} which is the required threshold statement. [guided] We put the pieces together. Dividing the variance bound $\operatorname{Var}(X) \leq \mathbb{E}[X] + 3 n^4 p^5$ by $(\mathbb{E}[X])^2$, \begin{align*} \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2} \leq \frac{1}{\mathbb{E}[X]} + \frac{3 n^4 p^5}{(\mathbb{E}[X])^2}. \end{align*} The first term tends to zero because $\mathbb{E}[X] \geq (np)^3/48 \to \infty$ (we established $np \to \infty$ as the hypothesis of the supercritical case). For the second term, use the lower bound $(\mathbb{E}[X])^2 \geq n^6 p^6 / 2304$: \begin{align*} \frac{3 n^4 p^5}{(\mathbb{E}[X])^2} \leq \frac{3 n^4 p^5 \cdot 2304}{n^6 p^6} = \frac{6912}{n^2 p}. \end{align*} Now $n^2 p = n \cdot (np) \to \infty$ since $np \to \infty$ and $n \to \infty$, so this term also tends to zero. Both terms vanishing gives $\operatorname{Var}(X)/(\mathbb{E}[X])^2 \to 0$, and the [second moment method](/theorems/2057) translates this into \begin{align*} \mathbb{P}(X = 0) \leq \frac{\operatorname{Var}(X)}{(\mathbb{E}[X])^2} \to 0, \end{align*} hence $\mathbb{P}(X \geq 1) \to 1$. Since $\{X \geq 1\} = \{K_3 \subseteq G\}$, we have established the supercritical limit $\mathbb{P}(K_3 \subseteq G) \to 1$ when $p \gg 1/n$. Together with the subcritical limit from Step 2, this is exactly the threshold statement of the theorem. [/guided] [/step]