Prüfer Sequences
Table of Contents

Prüfer Sequences

Definition: For a tree graph $G$ on $n$ labelled vertices, the Prüfer Sequence of $G$ is a sequence containing $n-2$ entries of $\{1, 2, ..., n \}$ labelled vertices that is unique to $G$ and is constructed by deleting the leaf in the graph with the smallest label and making the first entry in the sequence the vertex label that is adjacent to that vertex. The second entry of the Prüfer sequence comes from deleting the leaf with the second smallest label and making the second entry in the sequence the vertex label adjacent to that vertex, and so forth.

For example, let's look at the following labelled graph:

Screen%20Shot%202014-03-20%20at%203.17.43%20AM.png

The leaf with the smallest label is $1$, so let's delete that vertex and put $7$ as the first entry in our sequence since $7$ was adjacent to $1$. So far our sequence is $( 7 )$ and our graph is as follows:

Screen%20Shot%202014-03-20%20at%203.18.16%20AM.png

The next leaf with the smallest label is $2$. It's neighbour is $7$ as well, so our sequence so far is $(7, 7)$ and when we delete leaf $2$, we obtain the following graph:

Screen%20Shot%202014-03-20%20at%203.18.33%20AM.png

The next leaf with the smallest label is $4$, which is adjacent to $3$, so our sequence is now $(7, 7, 3)$. Deleting the leaf we obtain the following graph:

Screen%20Shot%202014-03-20%20at%203.18.56%20AM.png

The next leaf with the smallest label is $5$ which is adjacent to $3$, so our sequence is $(7, 7, 3, 3)$. Deleting the leaf we obtain the following graph:

Screen%20Shot%202014-03-20%20at%203.19.31%20AM.png

And lastly, the leaf with the smallest label is $6$, which is also adjacent to $3$, so our sequence is $(7, 7, 3, 3, 3)$. We are now done with the following graph:

Screen%20Shot%202014-03-20%20at%203.19.51%20AM.png

So our Prüfer Sequence for the original graph is $(7, 7, 3, 3, 3)$.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License