# How to show the small component is likely to be a tree in a random graph

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

• The "supercritical regime" is not the same as $np > 1$. For example, if $p = \frac1n + \frac1{n^2}$, we are still within the critical window and there is no giant component. – Misha Lavrov Mar 10 at 0:48

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.