Motivation
How many trees can be drawn on the vertex set ? For the answer is three: a tree on three vertices is a path, and it is determined by its middle vertex. For there are two shapes, a path and a star. There are labeled paths, because reversing the vertex order gives the same path. There are labeled stars, one for each choice of center. The total is . The pattern , suggests the count .
Counting the trees shape by shape becomes hopeless quickly, because the number of shapes grows and each shape has its own symmetries. A better strategy is to build a bijection. The number counts sequences of length with entries in . So we want a rule that turns each labeled tree into such a sequence, and a second rule that turns each sequence back into a tree, with each rule undoing the other. The Prüfer encoding is such a pair of rules. The real content of this chapter is the proof that the two algorithms are inverse, and that proof depends on one fact: the code records the degrees of the tree.
Definitions
Definition 1.5.1
(Labeled tree and leaf)
A labeled tree on a finite set of positive integers is a simple undirected graph with vertex set that is connected and acyclic. Our main case is . Since the algorithms are applied to subtrees whose vertex sets are no longer initial segments, we allow any such with the ordering inherited from the integers. Two labeled trees are equal when they have the same edge set. This is strictly finer than isomorphism.
A leaf is a vertex of degree . The one-vertex tree has a single vertex of degree , so it has no leaves at all. For this reason the algorithms below require , and the case is handled separately.
We use three standard facts about a tree with vertices:
- has exactly edges, so .
- has at least two leaves. To see this, take a longest path. Each endpoint has no neighbor off the path, since that would give a longer path, and no second neighbor on the path, since that would give a cycle.
- If is a leaf, then is a tree on . Deleting a degree-one vertex cannot create a cycle or disconnect the other vertices.
For a finite sequence and a value , write for the number of entries of equal to . Write for the set of values that occur in .
Definition 1.5.2
(Prüfer encoder)
Let be a tree on with . Put . For , carry out three steps:
- let be the smallest leaf of ;
- record its unique neighbor ;
- set .
The output is .
Definition 1.5.3
(Prüfer decoder)
Let have entries in , where . Put , and write for the remaining suffix. For , carry out three steps:
- let ;
- add the edge ;
- set and drop from the suffix.
When the suffix is empty, join the two labels of by an edge. The output graph is .
Both algorithms are recursive in a precise sense. After its first step, the encoder of continues exactly as the encoder of would. After its first step, the decoder of on continues exactly as the decoder of on would.
The encoder is well defined
Lemma 1.5.4
(Encoder invariant)
For each , the graph is a tree on vertices. Consequently every step is defined, has length exactly , and is a single edge.
Proof
(Induction on the number of deletions)
We use induction on . The case holds because . Suppose is a tree on vertices, where . Then , so by Fact 2 a leaf exists. The smallest leaf is therefore well defined, and so is its unique neighbor . By Fact 3, is a tree on vertices.
The loop runs exactly times and records one entry per step, so the length is . The final tree has two vertices, so it is a single edge.
Theorem 1.5.5
(The code records degrees)
For every vertex ,
In particular, the leaves of are exactly the vertices of that do not appear in .
Proof
(Counting the edges at a vertex)
Step deletes exactly one edge, namely . After the last step a single edge remains. Every edge of is therefore either deleted at exactly one step or is the final edge.
Fix and count the edges of at . There are two cases.
Case 1: for some . At step , the vertex is a leaf of , so exactly one of its edges survives up to step . That edge is deleted at step , and in that step is the deleted leaf, not the recorded neighbor. The remaining edges at were deleted at earlier steps . In each such step the deleted leaf is not , because is still present, so the edge meets only if . Conversely, each step with deletes an edge at . After step the vertex is gone and never appears again. Hence .
Case 2: is one of the two final vertices. The vertex has degree in . The same argument shows that exactly of its edges were deleted at steps with .
The second sentence of the theorem follows because if and only if .
The degree-recording theorem applies to every tree, including . The code of is the suffix . So the leaves of are exactly the vertices of that are absent from the remaining suffix. This is precisely the rule the decoder uses.
The decoder is well defined and outputs a tree
Lemma 1.5.6
(Decoder invariants)
For each , the following hold before step :
- (I1) ;
- (I2) every entry of lies in .
Consequently:
- (a) the candidate exists;
- (b) and , so no loop is created;
- (c) , so the recorded neighbor remains available.
At the end, has two distinct elements. Each label of is either removed exactly once as some or belongs to the final pair, and has edges.
Proof
(Induction on the decoder step)
Both invariants hold for : , and the entries of lie in .
Assume (I1) and (I2) hold before step . The suffix has entries, so it contains at most distinct values. Since , some element of is absent from the suffix, which proves (a).
The entry lies in by (I2). It differs from because was chosen absent from , and is the first entry of . This proves (b), and (c) follows.
To check that the invariants persist, note that . Every entry of was an entry of , so it lies in , and it is not , so it lies in .
Labels leave only by being chosen, and they never re-enter, so no label is chosen twice. After removals, two labels remain, and these are joined by the final edge. The decoder adds edges in the loop and one final edge, for a total of .
Theorem 1.5.7
(The decoder outputs a tree)
is a labeled tree on .
Proof
(Downward induction on attached vertices)
For , let be the graph on whose edges are the final edge together with for . These edges really lie inside : for , both and belong to .
The graph is a single edge, which is a tree. The graph is obtained from by adding the new vertex and the single edge , where by part (c) of the decoder-invariant lemma. Attaching a new vertex by one edge to a tree gives a tree. By downward induction is a tree on .
The decoded tree also has degrees determined by the sequence. This can be checked from the decoder alone, without using the encoder.
Lemma 1.5.8
(Decoded degrees)
In , every satisfies .
Proof
(Counting the edges at a decoded vertex)
The edges of are the together with the final edge. They are pairwise distinct: if , the earlier removed label is absent from , while both endpoints of the later edge lie in . The final edge also has both endpoints in , so it differs from the earlier edge.
The edge meets if or , and never both, by part (b) of the decoder-invariant lemma. Each index with contributes one edge at .
In addition, exactly one of the following holds: either for a single , or lies in the final pair. Either way this contributes exactly one more edge at .
The two algorithms are inverse
Theorem 1.5.9
(Encoding and decoding are inverse)
For every finite with :
- for every tree on ;
- for every sequence .
Proof
(Induction on the number of vertices)
Both parts use induction on , over all vertex sets of size at once.
For , the only sequence is the empty one. The only tree on is its single edge. The decoder joins the two labels, so both identities hold.
Now let .
Part 1. Let . By the degree-recording theorem, is the set of leaves of . So the decoder's first choice is , and it adds the edge , which is an edge of .
The rest of the decoder run is the decoder of on . By the definition of the encoder, that sequence is . By induction the remaining run outputs . Hence
Part 2. Let . By the decoded-degree lemma, the leaves of are exactly , so the smallest leaf is . The edge lies in and is a leaf, so the encoder records .
Deleting removes only the edge . What remains is exactly the graph that the decoder of builds on . By induction, the encoder applied to it returns . So .
Proof X-ray
One fact from each side
The proof needs one fact about each algorithm, and each part uses only its own. Part 1 uses the degree-recording theorem, a statement about alone, to show that the decoder's first choice is the encoder's first deletion . Part 2 uses the decoded-degree lemma, a statement about alone, to show that the encoder's first deletion is . Neither part assumes the identity it is proving, so the argument is not circular.
The key move is the same in both parts: the leaves of a tree are exactly the labels absent from its code, so “smallest absent label” and “smallest leaf” pick the same vertex. After one step each algorithm continues on or , a set of size that is usually no longer an initial segment of the integers; this is why the induction runs over all vertex sets of a given size at once, and the base case closes it.
Cayley's formula and degree sequences
Theorem 1.5.10
(Cayley's formula)
For , the number of labeled trees on is . For this equals , the single edge . For there is exactly one tree, the edgeless graph on , which is connected and acyclic.
The inverse theorem gives a bijection between the trees on and the set , which has elements. The case is settled by direct inspection, not by the formula. The encoding argument does not apply when : a sequence cannot have length , and the encoder is undefined there.
Theorem 1.5.11
(Trees with prescribed degrees)
Let and let be integers. If every and , then the number of trees on with for all is
Otherwise the number is .
By the degree-recording theorem and the inverse theorem, such trees correspond to sequences of length in which each occurs exactly times. The prescribed multiplicities add up correctly:
The number of arrangements is therefore the stated multinomial coefficient. If some , it cannot be a graph degree. If some , the vertex would be isolated, which is impossible in a connected graph with vertices. If the sum is wrong, Fact 1 fails. In either case there are no such trees.
Worked examples
Worked example 1.5.12
(Stars and paths)
Stars. Let be the star on with center , where . Every vertex other than is a leaf, and deleting leaves keeps as the center. So every recorded neighbor is , and
with entries. This agrees with the degree-recording theorem, since .
Paths. Consider the path . The smallest leaf is always the current left end, so the code is .
Now consider the relabeled path . Its leaves are and . Deleting records . Then becomes a leaf, and deleting records . The code is , while the path has code . The two trees are isomorphic, but they are different labeled trees, and their codes differ.
Worked example 1.5.13
(Encoding a tree on seven vertices)
Let have edges . Its degrees are , , and all other vertices have degree .
| Step | Current leaves | Delete | Record |
|---|---|---|---|
| 1 | |||
| 2 | |||
| 3 | |||
| 4 | |||
| 5 |
The vertices and remain. The code is . As the degree-recording theorem predicts, and appear twice, appears once, and the leaves never appear.
Worked example 1.5.14
(Decoding a sequence)
Decode on .
| Step | Remaining labels | Suffix | Absent labels | New edge |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 3 | ||||
| 4 | ||||
| 5 |
The final edge is . The output has the six edges .
At step 4, label becomes available only after both copies of have left the suffix. To check the result, re-encode the tree. The deletions are in that order, and the recorded neighbors are , which is exactly .
Counterexamples and limits
Counterexample mode
Changing the leaf rule
For the path , the "smallest leaf" rule gives . A "largest leaf" rule deletes first and gives . A rule that allows "any leaf" does not even define a function, because one tree would receive both codes. The bijection depends on the exact rule and on the ordering of the labels.
The count is equally tied to the complete graph: it enumerates spanning trees of and nothing else.
Counterexample mode
Spanning trees of other graphs
Cayley's formula counts spanning trees of the complete graph only. The -cycle with edges has exactly spanning trees, not . Decoding the sequence produces the edges , , and . The edge is not an edge of the cycle. Prüfer decoding is not an algorithm for enumerating the spanning trees of a general graph.
Common mistakes
Common mistake
(Testing against the whole original sequence)
The decoder must test absence from the remaining suffix. In the decoding example, label appears in the original sequence, yet it is correctly chosen at step 4, after both copies of have left the suffix.
Common mistake
(Counting shapes instead of labeled trees)
There are labeled trees on but only two unlabeled shapes, the path and the star. The formula does not count trees up to isomorphism, and Prüfer codes are not invariants of shape: the isomorphic paths and have codes and .
Finally, the algorithms are not inverse merely because both look reversible: without the degree-recording theorem and the decoded-degree lemma there is no reason the decoder's first choice should match the encoder's first deletion.
Practice
Quick check
(Let and . Count the labeled trees on in which vertex has degree .)
Solution
By the degree-recording theorem and the inverse theorem, we must count the sequences in with exactly entries equal to . First choose the positions of those entries in ways. Then fill each of the other positions with one of the labels . The count is
The range is exact. The lower bound holds because by connectivity. The upper bound holds because . The base is at least , so when the exponent is the factor is genuinely . For the only case is , which gives , the single edge.
As a check, take . The values give , , and , and . In general, the binomial theorem gives
Quick check
(Let be the tree on with edges . Compute , then decode the result and confirm that you recover .)
Solution
Encoding. The initial leaves are . The steps are:
- delete and record ; now is a leaf;
- delete and record ;
- delete and record ; now is a leaf;
- delete and record ; now is a leaf;
- delete and record ; now is a leaf;
- delete and record .
The vertices and remain. The code is . It has length , and , the only vertex of degree , appears twice.
Decoding. The successive absent sets are:
- , giving the edge ;
- , giving ;
- , giving ;
- , giving ;
- , giving ;
- , giving .
The final edge is . These seven edges are exactly the edges of .
Quick check
(List all labeled trees on and on with their codes. Decode on .)
Solution
On there is one tree, the edge , with the empty code. This matches .
On every tree is a path with some middle vertex . The middle vertex has degree and the other two vertices are leaves, so the code is . The three trees have codes , , and , which matches .
To decode on : the labels absent from the suffix are and , so the decoder joins to and leaves . The final edge is . The result is the path , whose middle vertex is , as expected.
Quick check
(Count the labeled trees on with degree sequence . Explain why no tree on has degree sequence .)
Solution
All degrees are at least , and the sum is . The prescribed-degree theorem therefore applies:
For the second sequence the sum is , so the count is .
Quick check
(Using the prescribed-degree theorem, show that carries labeled paths for .)
Solution
A tree is a path exactly when two vertices have degree and the rest have degree . Choose the two endpoints in ways. For each such choice, the prescribed-degree theorem gives
The total is .
This agrees with the earlier counts. For the formula gives . For it gives , which matches the Motivation. For it gives .
Related notes
Prerequisites: trees, leaves, and the edge count . This chapter leads on to degree-sequence enumeration and to spanning-tree counting in general graphs. The general problem requires methods other than Prüfer codes.