# Prüfer Sequence from Labeled Tree

## Contents

## 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 $\left({\mathbf{a}_1, \mathbf{a}_2, \ldots, \mathbf{a}_{n-2}}\right)$.

### 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 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 $\left({\mathbf{1}}\right)$.

### Iteration 2

**Step 1**: There are $7$ nodes, so continue to**step 2**.

**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 $\left({\mathbf{1}, \mathbf{7}}\right)$.

### Iteration 3

**Step 1**: There are $6$ nodes, so continue to**step 2**.

**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 $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}}\right)$.

### Iteration 4

**Step 1**: There are $5$ nodes, so continue to**step 2**.

**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 $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}, \mathbf{7}}\right)$.

### Iteration 5

**Step 1**: There are $4$ nodes, so continue to**step 2**.

**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 $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}}\right)$.

### Iteration 6

**Step 1**: There are $3$ nodes, so continue to**step 2**.

**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 $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.

### Iteration 7

**Step 1**: There are $2$ nodes, so**stop**.

The Prüfer sequence is $\left({\mathbf{1}, \mathbf{7}, \mathbf{5}, \mathbf{7}, \mathbf{7}, \mathbf{1}}\right)$.

## 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.