Prüfer Sequences

# 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: 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: 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: 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: 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: 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: So our Prüfer Sequence for the original graph is \$(7, 7, 3, 3, 3)\$.