I was just looking a book and the book said For a graph in supercritical regime (np > 1). For the small component (size s) not a part of giant component, it is a tree (which means the number of edges in the small component is s - 1). So, anyone who can tell me how to prove it?
Thanks
On
If you have an Erdős–Rényi random graph, one way to show this is true in expectation is to start with a tree and calculate the expected number of extra edge creating loops.
Consider an Erdős–Rényi random graph with $n$ vertices and probability $p$ of an edge between any pairs of vertices.
The expected degree, per vertex is given by
\begin{align*} d = \mathbb{E}[k] = \mathbb{E}[\frac{2m}{n}] = \frac{2\mathbb{E}[m]}{n} = \frac{2}{n}{n \choose 2}p = \left(n-1\right)p \end{align*}
This allows us to rewrite the probability parameter in terms of the expected degree as \begin{align*} p = \frac{d}{n-1} \end{align*}
Now suppose you are looking at small component that is a tree. If the small component contains $n_s$ vertices, then it must contain exactly $m_s = n_s -1$ edges. Now the we may ask, what is the expected number of extra edges one would observe?
There are ${n_s \choose 2}$ ways one could place an edge, and there are $n_s -1$ existing edges in the component, so the expected number of extra edges will simply be: \begin{align*} m_{\text{extra}}=\frac{(n_s-1)(n_s-2)}{2}\left(\frac{d}{n-1}\right) \end{align*}
So, in the limit of $n \rightarrow \infty$, (including $np>1$), the expected number of loop creating edges tends to $0$ and the component is a tree.
This is false. You can say that the small components are simple meaning that they contain at most one cycle, but you cannot guarantee that they are all trees.
For instance, let's consider $p = \frac cn$ (for any positive real $c$, whether it is bigger than $1$ or not) and count the components which are triangles. Let $X$ be the number of such components.
The probability that three given vertices induce a triangle component is $p^3 (1-p)^{3(n-3)} \sim p^3 e^{-3np} = p^3 e^{-3c}$ and since there are $\binom n3 \sim \frac{n^3}{6}$ ways to choose three vertices, we have (multiplying these together) $\mathbb E[X] \sim \frac{c^3}{6} e^{-3c}$.
To compute $\mathbb E[X^2]$, we count the number of ordered pairs of triangle components. There are $X$ pairs in which a component is paired with itself. As for pairs of two distinct components, there are $\binom n3 \binom{n-3}3 \sim \frac{n^6}{36}$ ways to choose their vertices, and the probability is $p^6 (1-p)^{6(n-6)+9} \sim p^6 e^{-6c}$ that any given choice induces two triangle components, so in expectation (by multiplying these together) there are $\frac{c^6}{36} e^{-6c}$ such pairs. Therefore $\mathbb E[X^2] \sim \frac{c^3}{6}e^{-3c} + \frac{c^6}{36} e^{-6c}$, and $\mathrm{Var}[X] \sim \frac{c^3}{6}e^{-3c}$.
Now apply the one-sided Chebyshev's inequality to conclude that $$ \Pr[X = 0] \le \frac{\mathrm{Var}[X]}{\mathbb E[X^2]} \sim \frac{\frac{c^3}{6}e^{-3c}}{\frac{c^3}{6}e^{-3c} + \frac{c^6}{36} e^{-6c}} = \frac{1}{1 + \frac{c^3}{6}e^{-3c}}. $$ For any constant $c>0$, this is bounded away from $1$ as $n \to \infty$, and so there is a constant positive probability of finding triangle components.
(These are only one example of non-tree small components; they are just the easiest to analyze.)