Section 3.1 Prüfer Codes
This section covers the Prüfer Code, a bijection between labelled trees and certain sequences of integers. This bijection allows us to prove Cayley's theorem, giving a count of such labelled trees.
Given a combinatorial structure, such as a graph or a tree, it is natural to ask how many of such structures there are. Often, there is no nice formula, for instance, for the number of different trees on \(n\) vertices there. But if the vertices are labelled, then it turns out there's a nice answer.
Definition 3.1.1. Labelled tree.
A labelled tree on \(n\) vertices is a tree with \(n\) vertices, which are labelled \(1,2,\dots,n.\)
Theorem 3.1.2. Cayley's Theorem.
There are \(n^{n-2}\) labelled trees on \(n\) vertices.
One more convenient way of writing down a labelled tree is to write down all the edges. If there tree has \(n\) vertices, then there are \(n-1\) edges, and writing down all the edges takes \(2n-2\) numbers between \(1...n\text{.}\) However, we see that we're writing down the same tree lots of different times, by changing the order of the edges, and which vertex from each edge we write first. Furthermore, not every sequence of \(2n-2\) numbers between \(1...n\) will result in a tree.
To fix this problem, we will write down the edges in a particular order. Every tree has at least two leaves, and deleting a leaf gives a small tree. We will use these facts to give a systematic ordering to the edges in a labelled tree, as follows: the first edge will be the edge connecting the leaf with the smallest label to the rest of the tree. We will record that edge, with the leaf on the bottom row, and the "parent" vertex, i.e., the vertex the leaf is connected to, in the top row. Deleting the leaf and the vertex gives a tree with one fewer vertex, and we iterate the process.
Algorithm 3.1.3. Pruning Algorithm.
Input: A labelled tree \(T\) on \(n\) vertices.
Output: A \(2\times n-1\) table with entries in \(\{1,\dots,n\}\) that records the edges of \(T\) in a specified order.
Find the leaf \(v\) with the lowest label; it will have one edge \(e\text{,}\) connecting it to some vertex (its "parent") \(w\text{.}\) Form a new tree \(T^\prime\) by deleting \(v\) and \(e\text{,}\) and record \(e\) in the output table, putting the deleted vertex \(v\) in the bottom row and its parent \(w\) above it in the top row.
This method fixes the problem of the ordering of the edges not being unique, but as of now we are still recording more information than needed. But note the following: since we delete a vertex when we put it in the bottom row, no number will appear twice on the bottom row. The last column is the last two vertices existing, and if we look at the bottom row and the last entry on the top row, we see that every number from 1 to \(n\) will appear exactly once in these spots.
Definition 3.1.4. Prüfer code.
If record the edges of a tree \(T\) as in the Pruning Algorithm, the first \(n-2\) number appear in the top row is the Prüfer code of \(T\)
To finish the proof of Cayley's Theorem, we need to show that the Prüfer code is a bijection. The easiest way to do this is to show that it has an inverse; that is, given any sequence of \(n-2\) numbers between 1 and \(n\text{,}\) we can construct a tree \(T\) have that sequence as its Prüfer code.
This is most easily done by filling in the \(n\) numbers we deleted from the table of edges to get the Prüfer code. We will in the numbers on the bottom row from left to right. The first number on the bottom row will be the lowest number that does not appear in the Prüfer code. Delete the first column, and then iterate -- the next number will be the lowest number we haven't used, and that doesn't appear in the remainder of the Prüfer code.
Another way to phrase the last line, is that the next number filled in is always the lowest number the doesn't appear as the bottom entry on one of the \(n-1\) columns.
Example 3.1.5.
Suppose \(T\) has Prüfer code 4,4,1,4,5,5. This code has length 6, so we looking to complete it by filling in numbers from 1 to 8. We illustrate the process step by step.
The lowest number that doesn't appear is 2, so we fill that in on the bottom of the first column. We no longer have to consider the 4 directly above this 2, as it is not the bottom element of its column.
| 4 | 4 | 1 | 4 | 5 | 5 | |
| 2 |
To fill in the next cell, we put the lowest number not occuring as the lowest element of a column, namely 3.
| 4 | 4 | 1 | 4 | 5 | 5 | |
| 2 | 3 |
And now the lowest term not on the bottom of its column is 6, so we add that:
| 4 | 4 | 1 | 4 | 5 | 5 | |
| 2 | 3 | 6 |
Now the only 1 appearing has an element beneath it, and so 1 gets added in the next column:
| 4 | 4 | 1 | 4 | 5 | 5 | |
| 2 | 3 | 6 | 1 |
And now all the 4s have been passed, so the next number is 4. We jump ahead and fill in the two numbers under 5 as well:
| 4 | 4 | 1 | 4 | 5 | 5 | |
| 2 | 3 | 6 | 1 | 4 | 7 |
The two numbers we haven't used yet are 5 and 8, so they are the entries in the last column, giving us the completed table of edges
| 4 | 4 | 1 | 4 | 5 | 5 | 8 |
| 2 | 3 | 6 | 1 | 4 | 7 | 5 |
Having constructed the table encoding all the edges, we can now draw the labelled tree with those edges
