# Degree distribution of uniform spanning trees of a complete graph

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!

## 1 Answer

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.

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