Trees in sparse random graphs
W. Fernandez de la Véga · Journal of Combinatorial Theory Series A · 1987
Abstract Let r be any integer ≥2. There exist absolute constants C1 and C2 such that if G(N, p) denotes the random graph on N=C1n vertices with edge probability p= C 2 r N and, for each n, Tn is a tree on n vertices with maximum degree ≤ r + 1, then the probability that G(N, p) contains Tn tends to 1 as n → ∞.