Chief Wahoo

Prüfer

💡


In this article I will make an interactive presentation of part of Prüfer’s proof (cough) of Cayley’s theorem on the enumeration of labelled trees.

tldr; skip to the fun bit

First things first

A tree is probably an intimately familiar structure if you’re reading this (whether you know it or not). We see them everywhere in computer applications. Directories are arranged in trees, homologous nested Python dicts could be described as trees, the class-subclasses structure forms a tree[1].

A tree is also the name of a mathematical object which bears some relation to the computery things mentioned above. A tree is the most simple type of graph — where a graph is just a set of vertices connected by a set of edges. Let’s define a tree slightly more formally.

Let be a graph with vertices. is a tree if it has edges and no cycles, ie. there is only one path from any given vertex to any other. Here’s a picture of what might look like:

G 1 2 1--2 7 3 2--3 6 2--6 4 3--4 5 3--5 5--7

Pick any two nodes, and observe there is only one set of edges that can be followed to get from one to the other. Simple enough. The graph below is not a tree, since there are two different paths between the red and blue nodes, ie. it has edges (where is the number of vertices):

G 1 2 1--2 4 4--1 3 2--3 3--4

Ok.

Now we have some vaguely mathematical definition of what a tree is, we only need to make one additional definition and we are set to dive into Prüfer. A labelled tree is a tree with vertices where each vertex is labeled

Let’s get rid of the colours and draw one way of labelling the tree we drew above.

G 1 4 2 5 1--2 3 3 2--3 6 7 2--6 4 6 3--4 5 1 3--5 7 2 5--7

Cool.

[1]This holds up to mixins, but not to diamond inheritance.

Prüfer left to right

Cayley’s theorem is that the number of labelled trees of vertices is simply . Prüfer presented his proof for this theorem in Archiv für Mathematik und Physik 27 in 1918, in the form of an algorithm that represents a labelled tree of vertices as a unique sequence of integers where . This is something that has a clear programming application; namely as a way to store a labelled tree, something that is not naturally amenable to a computer, as a sequence of integers, which is. Then, we have an extremely concise way to uniquely encode a labelled tree.

Here’s how; let be a tree with vertices , now let the vertex be the end-vertex with the smallest label, let the label be the label of the vertex adjacent to (we don’t need to care how is labelled) and make the first item in our sequence. Now remove the vertex and its incident edge. Rince and repeat, removing end-vertices and recording their adjacent higher-degree’d vertex in our sequence until only two vertices remain. Disgard these vertices. At this point we will have the Prüfer sequence that uniquely represents , that is . Read more here to see why this is a proof of Cayley[2].

[2]Basically, the cardinality of the set of Prüfer sequences representing labelled trees with vertices is .

Prüfer right to left

Since this sequence uniquely represents , the algorithm roughly presented above is a bijection, and can be “reveresed”. That is we can take a Prüfer sequence representing an unknown tree and use it to reconstruct the tree. Given a sequence of length , the technique is as follows; we draw vertices and label them . We then make a list and find the smallest number in the list that is not in the sequence (ie. the smallest end-vertex — sound familiar?), now we draw an edge from the vertex labelled to the vertex bearing the label of first entry in the sequence and drop the first entry from the sequence. As with the “left to right” algorithm, we repeat this until we have two numbers remaining in our list (remember our sequence only had elements) and draw an edge between the vertices labelled by those two remaining numbers. Bingo, we’ve got a labelled tree.

The fun bit

Now we’ve got Prüfer sequences in hand, it’s time for some fun. Type a sequence of integers into the box below and watch the worst graph layout algo draw a tree, just for you!