The Encoding Rule
A labeled tree can be recorded by a short list of labels rather than by listing all its edges. The Prüfer encoding produces this list by a fixed procedure: at each step, remove the leaf with the smallest label and record its neighbor. The choice of the least-labeled leaf makes the procedure deterministic, so the same labeled tree always gives the same sequence.
Throughout, graphs are finite and simple. A tree is a connected graph with no cycles. A leaf is a vertex of degree \(1\). A labeled tree has distinct labels on its vertices; when comparing labels, we use their usual numerical order. The encoding below is defined for trees with at least two vertices.
The label written at each step belongs to the neighbor, not to the leaf being removed. The sequence keeps the order in which labels are recorded, and a label may appear more than once. The process stops as soon as two vertices remain; the edge between those final vertices is not recorded.
For a tree with two vertices, no deletion is needed, so its Prüfer sequence is the empty sequence. A one-vertex tree has no leaf under the degree-\(1\) definition, so the stated procedure does not apply to it.
Why the Procedure Is Well-Defined
Proof. Let \(T\) be a tree and let \(v\) be a leaf. The graph \(T-v\) has no cycle, since any cycle in \(T-v\) would also be a cycle in \(T\). To show that \(T-v\) is connected, take any two vertices \(x,y\ne v\). Since \(T\) is connected, there is a path from \(x\) to \(y\) in \(T\). A leaf cannot occur as an internal vertex of a path, because an internal vertex of a path has two path-neighbors whereas \(v\) has only one neighbor. Since neither endpoint of this path is \(v\), the path avoids \(v\) and remains in \(T-v\). Thus \(T-v\) is connected and has no cycles, so it is a tree. If \(T\) has exactly two vertices, deleting one leaf leaves a single vertex, which is connected and has no cycles. \(\square\)
Proof. We first verify that whenever a tree has at least two vertices, it has a leaf. In fact, it has at least two. Choose a path with the greatest possible number of edges; such a path exists because the tree is finite. It has at least one edge because the tree is connected and has at least two vertices. Write its vertices in order as \(v_0,v_1,\ldots,v_k\), where \(k\ge1\). The endpoint \(v_0\) has no neighbor outside this path, since such a neighbor would extend the path. It has no neighbor \(v_i\) with \(i\ge2\), since the edges along the path from \(v_0\) to \(v_i\), together with \(v_iv_0\), would form a cycle. Therefore \(v_0\) has only the neighbor \(v_1\), so it is a leaf. The same argument applies to \(v_k\); the two endpoints are distinct, giving at least two leaves.
Now start with \(n\ge2\) vertices. Whenever the current tree has more than two vertices, the preceding argument guarantees at least one leaf, and its finite set of leaf labels has a unique least element. The rule therefore selects exactly one leaf. By the Lemma, deleting it leaves a tree. Each step reduces the number of vertices by exactly one, so after \(n-2\) steps the remaining tree has \(n-(n-2)=2\) vertices. The procedure stops there, and one label was recorded at each step. Hence the sequence has exactly \(n-2\) entries. For \(n=2\), this gives zero steps and the empty sequence, as specified. \(\square\)
Tracing the Deletions
Worked Example: Encoding a Path on Six Vertices
Let \(T\) have vertex set \(V(T)=\{1,2,3,4,5,6\}\) and edge set \(E(T)=\{12,23,34,45,56\}\). These edges form the path \(1-2-3-4-5-6\), so \(T\) is connected and has no cycle. Apply the least-labeled-leaf rule.
| Step | Leaves before deletion | Leaf removed | Neighbor recorded | Edges remaining |
|---|---|---|---|---|
| 1 | \(\{1,6\}\) | \(1\) | \(2\) | \(\{23,34,45,56\}\) |
| 2 | \(\{2,6\}\) | \(2\) | \(3\) | \(\{34,45,56\}\) |
| 3 | \(\{3,6\}\) | \(3\) | \(4\) | \(\{45,56\}\) |
| 4 | \(\{4,6\}\) | \(4\) | \(5\) | \(\{56\}\) |
After the fourth deletion, vertices \(5\) and \(6\) remain, so the procedure stops. Reading the recorded neighbors in order gives the Prüfer sequence \((2,3,4,5)\).
Check: The tree has \(n=6\) vertices, and the sequence has \(4\) entries; the formula gives \(n-2=6-2=4\). Each entry is the neighbor of the leaf removed in that row, and the last remaining edge is \(56\).
Worked Example: Repeated Labels in the Sequence
Let \(T\) have \(V(T)=\{1,2,3,4,5,6,7\}\) and \(E(T)=\{14,24,34,45,56,57\}\). The graph is connected: vertices \(1,2,3\) attach to \(4\), and the branch from \(4\) continues through \(5\) to \(6\) and \(7\). These branches contain no cycle, so this is a tree.
| Step | Leaves before deletion | Leaf removed | Neighbor recorded | Edges remaining |
|---|---|---|---|---|
| 1 | \(\{1,2,3,6,7\}\) | \(1\) | \(4\) | \(\{24,34,45,56,57\}\) |
| 2 | \(\{2,3,6,7\}\) | \(2\) | \(4\) | \(\{34,45,56,57\}\) |
| 3 | \(\{3,6,7\}\) | \(3\) | \(4\) | \(\{45,56,57\}\) |
| 4 | \(\{4,6,7\}\) | \(4\) | \(5\) | \(\{56,57\}\) |
| 5 | \(\{6,7\}\) | \(6\) | \(5\) | \(\{57\}\) |
The final vertices are \(5\) and \(7\). The recorded sequence is \((4,4,4,5,5)\). In particular, a sequence entry can repeat: three successive deleted leaves have neighbor \(4\), and the last two have neighbor \(5\).
Check: There are \(7\) vertices and \(5\) recorded labels, and \(7-2=5\). The final edge \(57\) joins the two remaining vertices, as the stopping rule requires.
Worked Example: The Least Label Can Be in a Different Branch
Let \(T\) have \(V(T)=\{2,4,7,9,12,15\}\) and \(E(T)=\{27,47,79,9\,12,9\,15\}\), where \(9\,12\) denotes the edge \(9\)-\(12\), and \(9\,15\) denotes \(9\)-\(15\). The graph is the tree with branches \(2-7\), \(4-7\), \(7-9-12\), and \(7-9-15\): it is connected and has no cycle.
| Step | Leaves before deletion | Leaf removed | Neighbor recorded | Edges remaining |
|---|---|---|---|---|
| 1 | \(\{2,4,12,15\}\) | \(2\) | \(7\) | \(\{47,79,9\,12,9\,15\}\) |
| 2 | \(\{4,12,15\}\) | \(4\) | \(7\) | \(\{79,9\,12,9\,15\}\) |
| 3 | \(\{7,12,15\}\) | \(7\) | \(9\) | \(\{9\,12,9\,15\}\) |
| 4 | \(\{12,15\}\) | \(12\) | \(9\) | \(\{9\,15\}\) |
Vertices \(9\) and \(15\) remain, and the sequence is \((7,7,9,9)\). At step 3, the leaf \(7\) is chosen because it is the least label among \(7,12,15\), even though it is not an endpoint in the original drawing one might have in mind.
Check: The tree has \(6\) vertices, so the sequence must have \(6-2=4\) entries; the table has four. The entries \(7,7,9,9\) are respectively the neighbors of \(2,4,7,12\) at the times those leaves are removed.
How to Keep the Encoding Accurate
The procedure has two separate choices to track: which leaf is removed, and which label is recorded. The least-label rule applies to the current leaves, not to all vertices. After a deletion, degrees can change, so the leaf set must be updated before the next choice. The recorded label is the unique neighbor in the current tree at that step.
A reliable hand calculation keeps the current vertex and edge sets visible. At each step, identify all current leaves, select the smallest label in that set, find its neighbor using the current edge set, record that neighbor, and delete the selected leaf and its incident edge. The original graph may help orient the calculation, but it is the changing tree that determines each step.
Common mistake: recording the leaf instead of its neighbor. For the path with vertices \(\{1,2,3,4,5\}\) and edges \(\{12,23,34,45\}\), the least leaf at the first step is \(1\), whose neighbor is \(2\). After deleting \(1\), the least leaf is \(2\), whose neighbor is \(3\). Next, leaf \(3\) is removed and its neighbor \(4\) is recorded. The correct sequence is therefore \((2,3,4)\), not \((1,2,3)\). The incorrect list records the removed labels and does not follow the definition.
The order rule matters as well. In the same path, both end vertices are leaves initially, but the procedure chooses \(1\), not \(5\), because \(1<5\). Choosing a different leaf would be a different procedure; it would not be the least-labeled-leaf encoding specified here. In examples with several leaves, writing out the full current leaf set makes this convention explicit and prevents an accidental choice based on visual position.
What the Sequence Records
The Prüfer sequence is a compact record created by a local operation on the tree: one label is added for each deleted leaf, and the label added describes that leaf’s neighbor at that moment. The process does not record the deleted leaf itself, nor does it list every edge directly. Its fixed choice rule is useful when comparing or storing labeled trees, since it gives a consistent output for any input tree in the stated domain.
For a quick final audit, check three things: every selected vertex was a leaf in the current tree; each written label was its neighbor; and the number of entries is \(n-2\). The last check follows from deleting one vertex at a time until exactly two remain. These checks catch many bookkeeping errors without changing the encoding rule.
Check Your Understanding
For each question, apply the rule to the current tree at every step; do not choose leaves from the original edge list after they have been deleted.
- Encode the tree with \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). List the leaf set at each step and give the final two vertices.
- For \(V=\{1,2,3,4,5\}\) and \(E=\{13,23,34,35\}\), which label is recorded at the first step? Continue to obtain the whole sequence.
- A tree has \(8\) vertices. How many labels does its Prüfer sequence contain, and how many leaf deletions are performed?
- Explain why a label written in the sequence is the neighbor of the removed leaf rather than the removed leaf itself.
- Why must the leaf set be recomputed after each deletion? Give an example of a label whose degree changes during the procedure in one of the worked examples.