Degrees and Prüfer Sequences
A Prüfer sequence compresses information about a labeled tree into a list of vertex labels. One of its most useful features is that the list records degrees directly: a vertex of degree \(d\) occurs \(d-1\) times. This gives a quick consistency check for a proposed encoding and lets us read off the degree of every vertex without first reconstructing all the edges. The frequency check is useful, but it does not by itself verify that a particular sequence is the encoding of a particular tree; the order of the deletions matters too.
At each step the graph remaining after deletion is still a tree: deleting a leaf cannot disconnect any two remaining vertices, and cannot create a cycle. Thus, while more than two vertices remain, there is a leaf to delete. The labeling is part of the procedure: “smallest” always means smallest label among the leaves in the current tree.
The Degree–Frequency Theorem
Proof. Fix a vertex \(v\). While \(v\) remains in the tree, its current degree is its original degree minus the number of times it has already been recorded. Indeed, whenever a leaf adjacent to \(v\) is deleted, the edge from that leaf to \(v\) is removed and \(v\) is recorded once; this decreases the current degree of \(v\) by one. A deletion not adjacent to \(v\) neither changes its degree nor records it. This accounts for every deletion while \(v\) remains.
If \(v\) is deleted before the process stops, it is deleted as a leaf, so its current degree immediately before deletion is \(1\). The invariant just established gives \(1=\deg_T(v)-c(v)\), where \(c(v)\) is now its total number of appearances: after \(v\) is deleted, it cannot be recorded again. Hence \(c(v)=\deg_T(v)-1\). If \(v\) is one of the final two vertices, it is never itself deleted. When the process stops, the remaining tree consists of the single edge between those two vertices, so \(v\)'s current degree is \(1\). The invariant then gives \(1=\deg_T(v)-c(v)\) for its total number of appearances as well. In both cases \(c(v)=\deg_T(v)-1\). This also covers \(n=2\): both vertices have degree \(1\), and neither appears in the empty sequence. \(\square\)
Proof. By the theorem, a vertex \(v\) is absent exactly when \(c(v)=0\), which holds exactly when \(\deg_T(v)-1=0\), or \(\deg_T(v)=1\). This is precisely the definition of a leaf. \(\square\)
To read degrees from a sequence, count each label’s appearances and add \(1\). A label that never appears has degree \(1\), not degree \(0\). A useful first check for any sequence claimed to encode a tree is that its length is \(n-2\), its entries are labels from \([n]\), and the degrees inferred from the frequencies are positive integers. Those checks are necessary; to verify the encoding of a specified tree, also run the prescribed smallest-leaf deletion procedure.
Encoding Trees Step by Step
Worked Example: A Seven-Vertex Tree
Let \(T\) have vertex set \(V(T)=\{1,2,3,4,5,6,7\}\) and edge set \(E(T)=\{14,24,35,45,56,57\}\). Its degrees are \(\deg(1)=1,\ \deg(2)=1,\ \deg(3)=1,\ \deg(4)=3,\ \deg(5)=4,\ \deg(6)=1,\ \deg(7)=1\). The graph is connected, and it has six edges on seven vertices with no cycle; it is a tree.
Now encode it. Each row gives the remaining vertices and edges before deletion, all current leaves, the deleted leaf, and the recorded neighbor.
| Step | Remaining vertices | Remaining edges | Leaves | Delete; record |
|---|---|---|---|---|
| 1 | \(\{1,2,3,4,5,6,7\}\) | \(14,24,35,45,56,57\) | \(\{1,2,3,6,7\}\) | Delete \(1\); record \(4\) |
| 2 | \(\{2,3,4,5,6,7\}\) | \(24,35,45,56,57\) | \(\{2,3,6,7\}\) | Delete \(2\); record \(4\) |
| 3 | \(\{3,4,5,6,7\}\) | \(35,45,56,57\) | \(\{3,4,6,7\}\) | Delete \(3\); record \(5\) |
| 4 | \(\{4,5,6,7\}\) | \(45,56,57\) | \(\{4,6,7\}\) | Delete \(4\); record \(5\) |
| 5 | \(\{5,6,7\}\) | \(56,57\) | \(\{6,7\}\) | Delete \(6\); record \(5\) |
The two final vertices are \(5\) and \(7\), joined by edge \(57\). The recorded entries, in order, give the Prüfer sequence \((4,4,5,5,5)\), which has \(7-2=5\) entries. The frequencies are \(c(4)=2,\ c(5)=3\), and \(c(1)=c(2)=c(3)=c(6)=c(7)=0\). Adding one gives degrees \(3,4,1,1,1,1,1\) at the corresponding vertices, agreeing with the edge list.
Check: The degree sum is \(1+1+1+3+4+1+1=12\), and the edge list has \(6\) edges, so the degree sum is \(12=2\cdot6\). The sequence has \(5\) entries, and the frequency sum is \(2+3=5\), as required.
Worked Example: The Prüfer Sequence of a Path
Let \(T\) have \(V(T)=\{1,2,3,4,5\}\) and \(E(T)=\{12,23,34,45\}\), the path \(P_5\). Its endpoint degrees are \(\deg(1)=\deg(5)=1\); the other degrees are \(\deg(2)=\deg(3)=\deg(4)=2\).
Initially the leaves are \(\{1,5\}\), so delete \(1\) and record its neighbor \(2\). The remaining vertices are \(\{2,3,4,5\}\) and the remaining edges are \(23,34,45\); the leaves are now \(\{2,5\}\). Delete the smallest leaf \(2\) and record \(3\). The remaining vertices are \(\{3,4,5\}\), with edges \(34,45\); the leaves are \(\{3,5\}\). Delete \(3\) and record \(4\). The final vertices are \(4,5\), joined by \(45\). Thus the sequence is \((2,3,4)\).
Its frequencies are \(c(2)=c(3)=c(4)=1\), while \(c(1)=c(5)=0\). Adding one gives degree \(2\) at vertices \(2,3,4\) and degree \(1\) at vertices \(1,5\), exactly as calculated from the edges. As an independent check, the degree sum is \(1+2+2+2+1=8=2\cdot4\), and the sequence length is \(3=5-2\).
Worked Example: Reading Degrees and Checking an Encoding
Let \(T\) have \(V(T)=\{1,2,3,4,5,6\}\) and \(E(T)=\{12,23,24,45,46\}\). The degrees from the edge list are \(\deg(1)=1,\ \deg(2)=3,\ \deg(3)=1,\ \deg(4)=3,\ \deg(5)=1,\ \deg(6)=1\).
Initially the leaves are \(\{1,3,5,6\}\). Delete \(1\), the smallest, and record \(2\). The remaining vertices are \(\{2,3,4,5,6\}\), with edges \(23,24,45,46\); the leaves are \(\{3,5,6\}\). Delete \(3\) and record \(2\). Now the remaining vertices are \(\{2,4,5,6\}\), with edges \(24,45,46\); the leaves are \(\{2,5,6\}\). Delete \(2\) and record \(4\). The remaining vertices are \(\{4,5,6\}\), with edges \(45,46\); the leaves are \(\{5,6\}\). Delete \(5\) and record \(4\), leaving the final edge \(46\). Therefore the sequence is \((2,2,4,4)\).
The frequencies are \(c(2)=2,\ c(4)=2\), and the other four labels have frequency \(0\). Adding one recovers degrees \(3\) at \(2\) and \(4\), and degree \(1\) at \(1,3,5,6\), matching the graph. The frequency sum is \(2+2=4=6-2\). The degree sum is \(1+3+1+3+1+1=10=2\cdot5\), as the edge list also has \(5\) edges.
Now consider the different sequence \((2,4,2,4)\). It has the same frequencies, so it implies the same degree list, but it is not the encoding of this particular tree. To see this, decode it by repeatedly joining the smallest remaining label absent from the current sequence to its first entry, then deleting that label and that first entry. From labels \(\{1,2,3,4,5,6\}\), the absent labels are \(\{1,3,5,6\}\): join \(1\) to \(2\). From the remaining labels \(\{2,3,4,5,6\}\), the remaining sequence is \((4,2,4)\), so the smallest absent label is \(3\): join \(3\) to \(4\). Next the labels are \(\{2,4,5,6\}\) and the sequence is \((2,4)\); the smallest absent label is \(5\), giving edge \(25\). Then the labels are \(\{2,4,6\}\) and the sequence is \((4)\); the smallest absent label is \(6\), giving edge \(64\). Join the last two labels \(2\) and \(4\). The decoded edges are \(12,34,25,46,24\), not \(12,23,24,45,46\). Thus frequencies check degrees but do not check the sequence’s deletion order.
Common Mistakes and Practical Checks
Omitting the extra one. A common wrong calculation is: “The label \(4\) occurs twice, so its degree is \(2\).” The theorem says \(c(4)=\deg(4)-1\), so the correction is \(\deg(4)=c(4)+1=2+1=3\). The reason for the extra one is that the vertex’s last incident edge remains when it is deleted as a leaf, or is the final edge if it survives to the last two vertices.
Not updating the leaf set. In the seven-vertex example, after the first three deletions the remaining edges are \(45,56,57\). The degrees in that remaining tree are \(1\) at \(4\), \(3\) at \(5\), and \(1\) at each of \(6\) and \(7\), so the leaves are \(\{4,6,7\}\). The next deletion must be \(4\), not \(6\). Updating the remaining graph before choosing the next smallest leaf is essential, even if a mistaken deletion order happens to produce the same recorded labels.
Confusing a degree check with an encoding check. The two sequences in the last example have identical frequencies, but decode to different trees. For a specified tree, verify the sequence by applying the smallest-leaf rule at every step; matching the frequency-derived degrees is a useful check, not a replacement for that procedure.
The frequency theorem is valuable because it turns sequence data into local structural information: it identifies leaves, gives every degree, and supplies a quick way to detect inconsistencies. For any tree on \(n\ge2\) vertices, the inferred degrees satisfy \(\sum_{v\in V(T)}(c(v)+1)=2(n-1)\), since a tree has \(n-1\) edges and the degree sum is twice the number of edges. Equivalently, the frequencies sum to \(n-2\), the length of the Prüfer sequence. These numerical checks are necessary conditions; the smallest-leaf procedure remains the definitive test for an encoding of a particular labeled tree.
Check Your Understanding
Use the degree–frequency theorem and, where relevant, trace the smallest-leaf rule.
- A tree on \(8\) vertices has a Prüfer sequence in which label \(6\) appears \(4\) times. What is \(\deg(6)\)?
- What does the absence of label \(3\) from the Prüfer sequence tell you about its degree, assuming the tree has at least two vertices?
- For the tree with vertex set \(\{1,2,3,4\}\) and edge set \(\{12,23,34\}\), compute the Prüfer sequence and check the degree–frequency relation at every vertex.
- Explain why a sequence of length \(n-2\) with the correct degree frequencies need not be the Prüfer sequence of a specified tree.
- Why does the theorem require \(n\ge2\), and what is the Prüfer sequence when \(n=2\)?