Inspired by this I am curious how to evaluate expected maximal vertices degree in uniform spanning trees. I am not able to add comments, therefore I had to ask a new question. Misha
We can also use Prüfer codes to answer questions about the joint distribution of degrees of multiple vertices in the same way.
How can we do that?
If we are picking a uniformly random labeled tree, this is the same as picking a uniformly random Prüfer code, and the maximum degree in the tree is one more than the maximum number of times that a label appears in the Prüfer code.
This is equivalent to the classic balls into bins problem: we are placing $n-2$ balls (the values of the Prüfer code) randomly into $n$ bins (the labels on the vertices) and we're looking for the maximum number of balls in a bin.
The Wikipedia article gives us a value of $(2+o(1))\frac{\log n}{\log \log n}$ for the maximum load when placing $n$ balls into $n$ bins. The answer with $n-2$ balls should be the same because the $2$ missing balls don't make a significant contribution asymptotically. (The $-1$ in the degree formula from the Prüfer code does not matter for the same reason.)
So with high probability, the maximum degree in the random tree is $(2+o(1))\frac{\log n}{\log \log n}$.
This also describes the expected value (which doesn't actually follow from the with high probability result, but it can be derived from the proof).