Embedding Spanning Trees in Random Graphs
Embedding Spanning Trees in Random Graphs
We prove that if T is a tree on n vertices with maximum degree $\Delta$ and the edge probability $p(n)$ satisfies $np\geq C\max\{\Delta\log n,n^{\epsilon}\}$ for some constant $\epsilon>0$, then with high probability the random graph $G(n,p)$ contains a copy of T. The obtained bound on the edge probability is shown …