The distribution of nodes of given degree in random trees

Let ??_n denote the set of unrooted unlabeled trees of size n and let k ≥ 1 be given. By assuming that every tree of ??_n is equally likely, it is shown that the limiting distribution of the number of nodes of degree k is normal with mean value ～ μ_kn and variance ～ σn with positive constants μ_k and σ_k. Besides, the asymptotic behavior of μ_k and σ_k for k → ∞ as well as the corresponding multivariate distributions are derived. Furthermore, similar results can be proved for plane trees, for labeled trees, and for forests. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 227–253, 1999