Cayley’s Formula From Prüfer Codes

From Codes to a Counting Formula

A tree on a fixed set of labels is determined by its edges, but listing all possible edge sets and testing which are trees quickly becomes impractical. Prüfer codes replace each tree by a short sequence of labels. The decisive fact is that this encoding is reversible: every sequence of the appropriate length decodes to exactly one tree, and every tree is recovered from its code. Counting sequences then counts trees.

Throughout, graphs are finite and simple. A tree is a connected graph with no cycles. Fix a label set \(L\) with \(|L|=n\). When \(n\ge2\), a leaf is a vertex of degree \(1\). To compare labels, give \(L\) a fixed order; for example, if \(L=\{1,\ldots,n\}\), use the usual numerical order. The rule “smallest leaf” refers to this order.

During decoding, the current sequence always consists of labels among the remaining vertices. Initially this is true by definition. At a step, the label deleted from the vertex set is absent from the current sequence, so deleting it cannot remove any label needed in the remaining sequence. Also, a label absent from a sequence of length \(r-2\) can always be chosen when \(r\) vertices remain: at most \(r-2\) distinct labels occur in that sequence, leaving at least two absent labels.

Why the Procedures Produce Trees

Proof. We use induction on \(r=|L|\), the number of labels being decoded. If \(r=2\), the sequence is empty and the procedure joins the two labels by one edge. This graph is connected and has no cycle, so it is a tree. Now suppose \(r\ge3\), and assume the claim for \(r-1\) labels. Let \(x\) be the smallest label absent from the sequence, and let \(a_1\) be its first entry. Since \(x\) is absent, \(a_1\ne x\). Decode the tail \(a_2,\ldots,a_{r-2}\) on the remaining \(r-1\) labels; by induction this gives a tree. Add the new vertex \(x\) and the edge \(xa_1\). The result is connected because \(x\) is joined to a vertex of the tree, and it has no cycle because \(x\) has just one incident edge. This is exactly the result of decoding the original sequence, so it is a tree. \(\square\)

We will use a degree-counting fact to verify that the two procedures undo one another. For a label \(v\), its number of occurrences in a sequence means the number of positions occupied by \(v\), counting repeated entries separately.

Proof. For decoding, induct on the number \(r\) of labels. With \(r=2\), both labels have degree \(1\) and occur zero times. For \(r\ge3\), let \(x\) be the label deleted at the first decoding step and \(a_1\) the first sequence entry. The decoded tree is formed from the tree decoded from the tail by adding \(x\) and the edge \(xa_1\). The label \(x\) has degree \(1\) and occurs zero times. For every other label \(v\), the new edge increases its degree by \(1\) exactly when \(v=a_1\); its occurrence count increases by \(1\) under exactly the same condition. The degree formula follows from the induction hypothesis.

For encoding, induct on the number \(r\) of vertices. When \(r=2\), the sequence is empty and both degrees are \(1\). For \(r\ge3\), let \(x\) be the deleted leaf and \(y\) its neighbor. The code starts with \(y\), followed by the code of the tree with \(x\) deleted. The label \(x\) occurs zero times and has degree \(1\). For any remaining label \(v\), deleting \(x\) reduces its degree by \(1\) exactly when \(v=y\), and adding the first code entry increases its occurrence count by \(1\) exactly when \(v=y\). The induction hypothesis therefore gives \(\deg(v)-1\) occurrences for each remaining label as well. \(\square\)

The Encoding and Decoding Are Inverse

Proof. First take an arbitrary sequence \(a_1,\ldots,a_{n-2}\) and decode it to a tree \(T\). By the degree-counting lemma, a label is absent from the sequence exactly when its degree in \(T\) is \(1\). Therefore the smallest label absent from the sequence is the smallest leaf of \(T\). In the recursive description of decoding, this leaf is \(x\), and its only edge is \(xa_1\). Encoding \(T\) thus deletes \(x\) first and records \(a_1\); what remains is precisely the tree decoded from the tail of the sequence. Repeating this argument recovers every entry in order. When two vertices remain, both procedures stop recording entries and use the edge between those vertices. Thus encoding the decoded tree returns the original sequence.

Now take a tree \(T\) and encode it. At any stage with \(r\ge3\) remaining vertices, the degree-counting lemma says that the labels absent from the remaining code are exactly the leaves of the remaining tree. Consequently, the smallest label absent from that code is the same smallest leaf that encoding deletes. The first remaining code entry is the neighbor recorded by encoding. Decoding therefore deletes the same leaf and adds the same edge at each such stage. This argument applies only while \(r\ge3\), when there is a first remaining code entry. After those deletions, the two remaining labels are the same as in the original tree, and decoding joins them by the original final edge. Hence decoding the encoded tree recovers \(T\). The two procedures are inverse, so the correspondence is a bijection. \(\square\)

The separate final-edge argument matters: when two vertices remain, the code is empty. There is no first code entry to use for another deletion. The last edge is determined by the two surviving labels.

Cayley’s Formula

Proof. By the bijection, counting trees on \(L\) is equivalent to counting sequences of length \(n-2\) whose entries are chosen from \(L\). There are \(n\) choices for each of the \(n-2\) positions, independently, so the number of sequences is \(n^{n-2}\). This proves the formula for \(n\ge2\). If \(n=1\), the single vertex with no edges is a tree, so there is exactly one; the exponent formula is stated separately because \(1-2\) is not a nonnegative sequence length. \(\square\)

What the Formula Counts—and a Common Error

The labels are fixed and distinct. Thus Cayley’s formula counts trees on those particular labels, not trees after identifying trees that differ only by a relabeling. The code records all the information needed to reconstruct the labeled tree; the bijection is why no trees are missed and no tree is counted twice.

A common error is to use \(n-1\) as the code length because every tree has \(n-1\) edges. These are different quantities: the code records one neighbor each time a leaf is removed, and the process stops with two vertices, so it makes \(n-2\) records. For \(n=4\), for instance, a code has two positions, each with four choices. The count is \(4\cdot4=4^2=16\), not \(4^3=64\). The bijection proves that the sequence length, rather than the number of tree edges, determines the exponent.

The formula also has a precise scope. For \(n\ge2\), the code consists of \(n-2\) entries from the fixed \(n\)-label set. For \(n=1\), the unique tree is handled separately. Keeping this endpoint distinct avoids assigning a negative length to a sequence.