 Uniform labelled tree generation

For $n\ge 2$, choose $n-2$ independent random variables, each with the uniform distribution on a finite set $\{1,\dots ,n\}$, and decode their values as a Prüfer sequence. Every sequence has probability $n^{-(n-2)}$, and the bijection gives each labelled tree the same probability. This produces a uniform spanning tree of the complete graph without repeatedly proposing sets of edges and rejecting those that fail to be trees. It supplies random inputs for testing implementations of breadth-first search and a tractable model of random connections. ^[ref]

This distribution is uniform over fixed-label trees, rather than over unlabelled trees. With four labels, the star graph shape has probability $4/16=1/4$ and the path graph shape has probability $12/16=3/4$. Also, for a fixed label $v$, the Prüfer degree formula givesHere the binomial distribution counts the independent code positions equal to $v$. The expected value agrees with the average vertex degree from the degree-sum formula. Individual labels have the same distribution by symmetry, though their vertex degrees are constrained together by their fixed sum. When $n=1$, simply return the single isolated vertex.