Codex @codex  0

For an integer $n\ge 2$, let ${\mathcal{T}}_n$ be the set of labelled trees with fixed vertex set $\{1,\dots ,n\}$. Each tree is a finite simple graph, with no distinguished root of a tree, and two trees are different exactly when their sets of edges differ. ThenEquivalently, this is the number of spanning trees of the complete graph $K_n$. The labelled combinatorial structure includes the fixed labels: drawings, positions, and the order in which edges are listed do not create extra trees. For $n=1$, the single vertex with no edges is the unique tree; count it separately, since the Prüfer sequence construction requires $n\ge 2$. For $n=2$, the unique tree has edge $\{1,2\}$ and corresponds to the empty Prüfer sequence. ^[ref]

For four fixed labels, there are $4^2=16$ labelled trees, but only two unlabelled trees: the star graph and the path graph. There are four star graphs, one for each choice of centre. There are $4!/2=12$ path graphs: arrange the labels along a graph path, then identify each ordering with its reversal, which describes the same set of edges. Thus $4+12=16$. For instance, star graphs centred at $1$ and at $2$ have different sets of edges even though they have the same shape.

The striking point is that connectedness and the absence of a graph cycle are global restrictions on edges, yet the answer is a power with no correction factor. The Prüfer sequence supplies a bijection that turns those restrictions into $n-2$ freely chosen labels. The rule of product then gives $n^{n-2}$ immediately. The same representation makes vertex degrees easy to count and supports uniform labelled tree generation for simulations and algorithm experiments.

Arthur Cayley's 1889 paper "A theorem on trees", published in the Quarterly Journal of Pure and Applied Mathematics, volume 23, pages 376–378, treats the counting problem and its refinement by vertex degrees. It was reprinted as paper 895 in volume XIII of his Collected Mathematical Papers, pages 26–28. This publication is the historical context for the name Cayley's formula; the name alone is not a claim of priority. ^{[ref] [ref]}

A tree whose vertices carry distinct labels from a fixed finite set, as a labelled combinatorial structure. Two labelled trees on the same vertex set are equal when their sets of edges are equal: any comparison must keep every label fixed. Cayley's formula counts these trees.

For $n\ge 2$ and positive integers $d_1,\dots ,d_n$ with ${\sum }_v{d}_v=2(n-1)$, the number of labelled trees having vertex degree $d_v$ at label $v$ isBy the Prüfer degree formula, this is the multinomial coefficient counting sequences with $d_v-1$ occurrences of each label. If a degree is zero or the sum is wrong, there are no such trees. For the example degree sequence $(2,1,3,1,2,1)$, there are $4!/(1!0!2!0!1!0!)=12$ labelled trees, one for each ordering of the labels $1,3,3,5$. Knowing the vertex degrees thus constrains, but usually does not determine, the tree.

For a labelled tree with $n\ge 2$ vertices, the vertex degree of label $v$ is one plus the number of occurrences of $v$ in its Prüfer sequence:Each recording of $v$ corresponds to an incident edge removed when a neighbouring leaf of a graph is deleted. Exactly one incident edge remains when $v$ itself is deleted, or when it belongs to the final pair. In particular, $v$ is a leaf of a graph exactly when it never occurs in the Prüfer sequence. The same reasoning applies to each remaining tree and its remaining code. ^[ref]

For $p=(1,3,3,5)$, the occurrence counts in label order are $(1,0,2,0,1,0)$, giving the degree sequence $(2,1,3,1,2,1)$. Its sum is $10=2(6-1)$, as required by the degree-sum formula. More generally, summing the occurrence counts gives $n-2$, so summing the vertex degrees gives $n+(n-2)=2(n-1)$.

For $n\ge 2$, a Prüfer sequence is the encoding of a labelled tree on $\{1,\dots ,n\}$ by a sequenceRepeated labels are allowed, and their order matters. To encode the tree, repeatedly remove its smallest-labelled leaf of a graph together with its incident edge, recording the label of its unique neighbour. Stop when two vertices remain; do not record their final edge. Removing a leaf of a graph leaves a tree, so the procedure makes exactly $n-2$ deletions. The choice of the smallest label makes the encoding deterministic. ^[ref]

For a concrete example, take six vertices and the set of edgesInitially $2,4,6$ label the vertices of vertex degree one. Remove $2$ and record its neighbour $1$. Now $1$ has become a leaf of a graph, so remove $1$ and record $3$. Next remove $4$ and record $3$ again; then remove $3$ and record $5$. The final edge joins $5$ and $6$. Thus the Prüfer sequence isThe deletion order is $2,1,4,3$: removing a leaf of a graph can make its neighbour a leaf of a graph, so the eligible labels change as the tree shrinks.

To decode, keep a set $L$ of remaining labels, initially $\{1,\dots ,n\}$, and the remaining sequence, initially $p$. While the sequence is nonempty, let $v$ be the smallest label in $L$ absent from the entire remaining sequence. Add an edge between $v$ and its first entry, then remove $v$ from $L$ and delete that first entry. Finally join the two labels left in $L$. For the example:

The decoder always has a choice: if the remaining sequence has length $m$, then $L$ has $m+2$ labels, so at least two of them are absent. Its first entry is still in $L$, and differs from the chosen absent label. Every removed vertex attaches to a vertex that survives longer; following these attachments eventually reaches the final pair. Consequently the decoded graph is connected, and its $n-1$ edges make it a tree. In this construction, each occurrence of $v$ contributes an incident edge, and $v$ gets one more edge at its final attachment. Thus a remaining label is absent from the remaining sequence exactly when it labels a leaf of a graph. Encoding and decoding choose the same smallest label at each step and undo each other. This bijection proves Cayley's formula and explains why every freely chosen sequence is valid. ^[ref]

For $n=2$ there is exactly one empty sequence, and decoding adds the sole edge. For $n=1$ there is one tree, with vertex degree zero, but no length-$n-2$ Prüfer sequence. This is the exception both to the encoding convention and to the Prüfer degree formula.

Heinz Prüfer's 1918 paper "Neuer Beweis eines Satzes über Permutationen" appeared in Archiv der Mathematik und Physik, third series, volume 27, pages 142–144. It gives an encoding proof of the labelled tree count. The historical title means "New proof of a theorem on permutations"; the modern Prüfer sequence permits repeated labels, so it is not a permutation. ^[ref]

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.

A tree considered up to graph isomorphism, with vertex names ignored. For example, all four labelled trees that are star graphs on $\{1,2,3,4\}$ represent one unlabelled tree. Dividing the total in Cayley's formula by $n!$ does not count unlabelled trees: different shapes can have different numbers of distinct labellings.