----- > [!proposition] Proposition. ([[small components of Erdos-Renyi random graph model are trees]]) > A [[small component]] of $G(n,p)$ becomes a [[tree]] as $n \to \infty$. > [!proof]- Proof. ([[small components of Erdos-Renyi random graph model are trees]]) > Consider a [[small component]] $A$ in $G(n,p)$ having $s$ nodes. $A$ has at least $s-1$ edges (else it would not be connected). We claim that it [[almost-everywhere|almost-surely]] does not have more than $s-1$ edges for $n \to \infty$. \ The probability of an edge existing between a specific node $i$ in $A$ and a specific node $j$ not in $A$ is $p=\frac{c}{n-1}$, where $c$ is the [[mean degree]] of $G(n,p)$. Let $X$ be a [[random variable]] corresponding to the number of additional edges (beyond the required $s-1$) in $A$. There are ${s \choose 2}- (s-1)=\frac{1}{2}(s-1)(s-2)$ choices for adding an edge in $A$. [[indicator random variable|Let]] $X_{k \ell}=\begin{cases}1 & \text{ if edge exists between } k, \ell \in A \\ 0 & \text{ if not.} \end{cases}$ Then $X=\sum_{}^{}X_{k \ell}$ and hence the [[expectation]] of $X$ is $\sum_{\frac{1}{2}(s-1)(s-2) \text{ terms}}^{}\mathbb{P}(X_{k \ell}=1)=\frac{1}{2}(s-1)(s-2) \frac{c}{n-1}.$ We see that as $n \to \infty$, $\mathbb{E}[X] \to 0$. Thus as $n \to \infty$, the number of edges in the small component $A$ [[converge|converges to]] precisely $s-1$, and we are done by [[tree iff has n-1 edges|tree iff has s-1 edges]]. ----- #### ---- #### References > [!backlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM [[]] > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ``` > [!frontlink] > ```dataview > TABLE rows.file.link as "Further Reading" > FROM outgoing([[]]) > FLATTEN file.tags as Tag > WHERE Tag = "#definition" OR Tag = "#theorem" OR Tag = "#MOC" OR Tag = "#proposition" OR Tag = "#axiom" > GROUP BY Tag > ```