Let $K_N$ be a complete graph with $N$ nodes. Consider the set consisting of all spanning trees of $K_N$, denoted by $\mathcal{T}_N$. What is the degree distribution of a tree $T$ selected uniformly at random from $\mathcal{T}_N$?

I know little about graph theory and I would appreciate A LOT if some experts can answer this question or lead me to the right place. Thanks!


Picking a uniformly random spanning tree of $K_n$ (in other words, a random labeled tree on vertex set $\{1,2,\dots,n\}$) is equivalent to choosing a uniformly random Prüfer code: $n-2$ independent, uniformly random integers from $\{1,2,\dots,n\}$.

Moreover, each vertex $i$ appears exactly $\deg(i)-1$ times in the Prüfer code.

The distribution of the number of appearances of a given value in a uniformly random Prüfer code is $\text{Binomial}(n-2, \frac1n)$ and therefore the degree distribution of a fixed vertex in a uniformly random spanning tree of $K_n$ is $1 + \text{Binomial}(n-2, \frac1n)$.

We can also use Prüfer codes to answer questions about the joint distribution of degrees of multiple vertices in the same way.

  • $\begingroup$ Perfect! It's great to know Prüfer code can be applied here. Thanks so much! $\endgroup$ – Zubat Mar 14 '18 at 23:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.