Prüfer Sequence from Labeled Tree

== Algorithm ==
Given a finite labeled tree, it is possible to generate a Prüfer sequence corresponding to that tree.
Let $T$ be a labeled tree of order $n$, where the labels are assigned the values $1$ to $n$.
:Step 1: If there are two (or less) nodes in $T$, then stop. Otherwise, continue on to step 2.
:Step 2: Find all the nodes of $T$ of degree $1$. There are bound to be some, from Finite Tree has Leaf Nodes. Choose the one $v$ with the lowest label.
:Step 3: Look at the node $v'$ adjacent to $v$, and assign the label of $v\,'$ to the first available element of the Prüfer sequence being generated.
:Step 4: Remove the node $v$ and its incident edge. This leaves a smaller tree $T'$. Go back to step 1.
The above constitutes an algorithm, for the following reasons:
=== Finiteness ===
For each iteration through the algorithm, step 4 is executed, which reduces the number of nodes by $1$.
Therefore, after $n - 2$ iterations, at step 1 there will be $2$ nodes left, and the algorithm will stop.
=== Definiteness ===
:Step 1: There are either more than $2$ nodes in a tree or there are $2$ or less.
:Step 2: There are bound to be some nodes of degree $1$, from Finite Tree has Leaf Nodes. As integers are totally ordered, it is always possible to find the lowest label.
:Step 3: As the node $v$ is of degree $1$, there is a unique node $v'$ to which it is adjacent. (Note that this node will not also have degree $1$, for then $v v'$ would be a tree of order $2$, and we have established from step $1$ that this is not the case.)
:Step 4: The node and edge to be removed are unique and specified precisely, as this is a tree we are talking about.
=== Inputs ===
The input to this algorithm is the tree $T$.
=== Outputs ===
The output to this algorithm is the Prüfer sequence $\tuple {\mathbf a_1, \mathbf a_2, \ldots, \mathbf a_{n - 2} }$.
=== Effective ===
Each step of the algorithm is basic enough to be done exactly and in a finite length of time.
== Example ==
Let $T$ be the following labeled tree:
:
This tree has $8$ nodes, so the corresponding Prüfer sequence will have $6$ elements.
=== Iteration 1 ===
: Step 1: There are $8$ nodes, so continue to step 2.
: Step 2: The nodes of degree $1$ are $8, 2, 6, 4, 3$. Of these, $2$ is the lowest.
: Step 3: $2$ is adjacent to $1$, so add $\mathbf 1$ to the Prüfer sequence.
: Step 4: Removing node $2$ leaves the following tree:
:
At this stage, the Prüfer sequence is $\tuple {\mathbf 1}$.
=== Iteration 2 ===
: Step 1: There are $7$ nodes, so continue to step 2.
: Step 2: The nodes of degree $1$ are $8, 6, 4, 3$. Of these, $3$ is the lowest.
: Step 3: $3$ is adjacent to $7$, so add $\mathbf 7$ to the Prüfer sequence.
: Step 4: Removing node $3$ leaves the following tree:
:
At this stage, the Prüfer sequence is $\tuple {\mathbf 1, \mathbf 7}$.
=== Iteration 3 ===
: Step 1: There are $6$ nodes, so continue to step 2.
: Step 2: The nodes of degree $1$ are $8, 6, 4$. Of these, $4$ is the lowest.
: Step 3: $4$ is adjacent to $5$, so add $\mathbf 5$ to the Prüfer sequence.
: Step 4: Removing node $4$ leaves the following tree:
:
At this stage, the Prüfer sequence is $\tuple {\mathbf 1, \mathbf 7, \mathbf 5}$.
=== Iteration 4 ===
: Step 1: There are $5$ nodes, so continue to step 2.
: Step 2: The nodes of degree $1$ are $8, 6, 5$. Of these, $5$ is the lowest.
: Step 3: $5$ is adjacent to $7$, so add $\mathbf 7$ to the Prüfer sequence.
: Step 4: Removing node $5$ leaves the following tree:
:
At this stage, the Prüfer sequence is $\tuple {\mathbf 1, \mathbf 7, \mathbf 5, \mathbf 7}$.
=== Iteration 5 ===
: Step 1: There are $4$ nodes, so continue to step 2.
: Step 2: The nodes of degree $1$ are $8, 6$. Of these, $6$ is the lowest.
: Step 3: $6$ is adjacent to $7$, so add $\mathbf 7$ to the Prüfer sequence.
: Step 4: Removing node $6$ leaves the following tree:
:
At this stage, the Prüfer sequence is $\tuple {\mathbf 1, \mathbf 7, \mathbf 5, \mathbf 7, \mathbf 7}$.
=== Iteration 6 ===
: Step 1: There are $3$ nodes, so continue to step 2.
: Step 2: The nodes of degree $1$ are $8, 7$. Of these, $7$ is the lowest.
: Step 3: $7$ is adjacent to $1$, so add $\mathbf 1$ to the Prüfer sequence.
: Step 4: Removing node $7$ leaves the following tree:
:
At this stage, the Prüfer sequence is $\tuple {\mathbf 1, \mathbf 7, \mathbf 5, \mathbf 7, \mathbf 7, \mathbf 1}$.
=== Iteration 7 ===
: Step 1: There are $2$ nodes, so stop.
The Prüfer sequence is $\tuple {\mathbf 1, \mathbf 7, \mathbf 5, \mathbf 7, \mathbf 7, \mathbf 1}$.
== Also see ==
Compare with the example given in Labeled Tree from Prüfer Sequence.
These two results are pulled together in Bijection between Prüfer Sequences and Labeled Trees.
Category:Tree Theory
Category:Combinatorics