In Erdos–Renyi random graphs $G(n, p)$; Can someone give me the idea on how to prove that if $p\times n^{\frac{k}{k-1}}= o(1),$ then there is no tree of order $k$?
The only hint that I can suppose is to use Cayley’s formula for to counting trees. But I don't know how to use it for to prove the above mentioned question.
Thanks!
Let $X$ denote the number of trees of order $k$. Then $E[X]$ is ${n \choose k} p^{k-1}f(k)$, where $f$ is the number of different possible trees on a set of $k$ vertices.
Since $\dbinom{n}{k} \leq {\left(\dfrac{ne}{k}\right)}^k$, the expectation is $n^kp^{k-1}g(k)$ where $g$ is some function of $k$. For the given range of $p$, and assuming $k$ constant, the expectation tends to zero as $n \to \infty$.
By Markov's inequality, $Pr[X \geq 1] \leq E[X]$ , hence $Pr[X \geq 1]=0$.