Grinberg-Introduction-Graph-Theory · Problem 5.30

Trees and arborescences

Mathematics — Graph Theory · counting-trees-by-degrees

Problem

Let n≥2n \geq 2 be an integer, and let d1,d2,…,dnd_1, d_2, \ldots, d_n be nn positive integers. An nn-tree shall mean a simple graph with vertex set {1,2,…,n}\{1, 2, \ldots, n\} that is a tree. We know from Corollary 5.14.9 that there are nn−2n^{n-2} many nn-trees. How many of these nn-trees have the property that deg⁡i=difor each vertex i ?\deg i = d_i \qquad \text{for each vertex } i\,?

Related theory

Browse the problem library