Counting Spanning Trees, A Neat Approach

In my last blog I commented on the relationship between a "parking sequence" problem for n cars and the number of spanning trees of degree n+1. Because I knew so little about the "WHY" of the counting method, I decided to read up a little on the proof for counting spanning trees. It turns out that Cayley [A. Cayley. A theorem on trees. Quart. J. Math., 23:376–378, 1889.] first proved the sequence, but the first combinatorial type proof was by Prufer in 1918 [H. Prufer. Never beweis eines satzes ¨uber permutationen. Arch. Math. Phys. Sci., 27:742–744,1918.] Prufer's method was so interesting, I thought I would share it with interested others who might not have come across it.

Prufer proved that the number of spanning trees for n nodes would be n^n-2 by showing that there is a bijection (For my students, you can think of that as sort of like a one-to-one function relationship) between the set of spanning trees and the number of ordered vectors (don't think that is how he said it) of length n-2 of the integers from one to n. For example, if n = 5, then the number of ordered triples (5-2) you could make with the integers 1 through 5 (allowing repetition) would count the number of spanning trees. To do it, he had to show that each spanning tree would produce a unique ordered n-2 tuple (is that a math word?) and that each such vector would produce a unique spanning tree.... and then he did... and since there are quite easily n choices for each of the n-2 spaces, the number of spanning trees must equal n^n-2.... admit it, that's pretty neat..

For a Spanning tree such as the one below the rules for deriving a code is to take the leaf (vertex with only a single edge to it) with the smallest number, and remove it, and record the vertex it is connected to. In the image, we would remove vertex 1, and write a 5. Now the lowest number on a leaf is 3, and it is connected to vertex 2, so we remove the vertex at 3 and our code is now 5,2. The next lowest leaf is 4, and it is also connected to vertex 2, so our code is now 5,2,2. At this point we have the n-2 terms we need for degree five.. and we can stop... I did some serious head scratching at this point about how he knew that we could ignore the remaining two vertices... but somehow, it all works... you can take the code and presto, you get all the vertices and edges...

Let's make up a code and see what happens... if we write (2,3,3) what spanning tree would it produce. Well, we know the degree of each vertex is one more than the number of times it appears on the code, so 1, 4, and 5 have degree 1 (they are leaves) and 2 has degree 2. Vertex 3 has degree 3, since it shows up 2 times in the code. We begin by remembering that the lowest numbered leaf (one) was removed first, so one must be connected to the vertex named first in our code, 2. Our next smallest leaf is vertex 4, so it must be connected to the vertex named second in the code, vertex 3. Finally we have vertex 5 as a leaf, and so we must have it connected to vertex 3 as well. Finally, we need to remember that the numbers in the code were connected to each other (hence the additional degree) and we should connect vertices 2 and 3.




But what if we changed the code to (3,2,3)? Same numbers, different order... We still have the same three leaves at 1, 4, and 5, but now 1 is connected to vertex 3; 4 connected to 2; and 5 would be connected to three.

What I haven't figured out yet (any help out there??) is how to find a bijection between the Prufer codes and the parking problem. More to learn....