Trees, counting
6a. Trees, examples
Trees, eventually. These are something beautiful, and difficult too, at the core of advanced graph theory. As starting point, we have the following definition:
A tree is a connected graph with no cycles. That is, there is no loop
As a basic example here, which is quite illustrating for how trees look, in general, we have the following beautiful graph, that we already met in chapter 4:
As already mentioned in chapter 4, such a graph is called indeed a tree, because when looking at a tree from the above, what you see is something like this.
Getting to work now, we can see right away, from Definition 6.1, where the difficulty in dealing with trees comes from. Indeed, with respect to what we did so far in this book, problems investigated, and solutions found for them, the situation is as follows:
(1) Most of our results so far were based on the correspondence between the graphs [math]X[/math] and their adjacency matrices [math]d[/math], which is something well understood, in general. However, for trees this correspondence is something quite tricky, because the loops of length [math]k[/math] are counted by the diagonal entries of [math]d^k[/math], and the condition that these entries must come only from trivial loops is obviously something complicated, that we cannot control well.
(2) Another thing that we did quite a lot, in the previous chapters, which was again of rather analytic type, in relation with the associated adjacency matrix [math]d[/math], was that of counting walks on our graphs. But here, for trees, things are again a bit complicated, as we have seen in chapter 1 for the simplest tree, namely [math]\mathbb Z[/math], and then in chapter 3 for the next simplest tree, namely [math]\mathbb N[/math]. So, again, we are led into difficult questions here.
In view of this, we will take a different approach to the trees, by inventing and developing the mathematics which is best adapted to them. As a first observation, both [math]\mathbb N[/math], [math]\mathbb Z[/math] and the snowflake graph above are special kinds of trees, having a root, like normal, real-life trees do. It is possible to talk about rooted trees in general, and also about leaves, cherries, and so on, and do many other tree-inspired things. Let us record some:
In relation with our notion of tree:
- We call rooted tree a tree with a distinguished vertex.
- We call leaf of a tree a vertex having exactly [math]1[/math] neighbor.
- With the convention that when the tree is rooted, the root is not a leaf.
In practice, it is often convenient to choose a root, and draw the tree oriented upwards, as the usual trees grow. Here is an example, with the root and leaves highlighted:
Along the same lines, simple facts that can be said about trees, we have as well:
A tree has the following properties:
- It is naturally a bipartite graph.
- The number of edges is the number of vertices minus [math]1[/math].
- Any two vertices are connected by a unique minimal path.
All this is elementary, and is best seen by choosing a root, and then drawing the tree oriented upwards, as above, the idea being as follows:
(1) We can declare the root, lying on the ground 0, to be of type “even”, then all neighbors of the root, lying at height 1, to be of type “odd”, then all neighbors of these neighbors, at height 2, to be of type “even”, and so on. Thus, our tree is indeed bipartite. Here is an illustration, for how this works, for the tree pictured before the statement:
(2) This is again clear by choosing a root, and then drawing our tree oriented upwards. Indeed, in this picture any vertex, except for the root, comes from the edge below it, and this correspondence between non-root vertices and edges is bijective. Here is an illustration, for how this works, for the same example of tree as before, with each edge being represented by an arrow, pointing towards the vertex it is in bijection with:
(3) Again, this is best seen by choosing a root, and then drawing our tree oriented upwards. Indeed, in this picture, traveling from one vertex to another, via the shortest path, is done uniquely, by going down as long as needed, and then up, in the obvious way. Here is an illustration for how this works, as usual for our favorite example of tree:
Thus, we are led to the conclusions in the statement.
Getting started for good now, let us look at the snowflake graph pictured before, with the convention that the graph goes on, in a 4-valent way, in each possible direction:
So, where does this beautiful graph come from, mathematically speaking? And a bit of thinking here leads to the following simple, and beautiful too, answer:
Consider the free group [math]F_N[/math], given by the following formula, with [math]\emptyset[/math] standing for the lack of relations between generators:
This is something quite basic, the idea being as follows:
(1) At [math]N=1[/math], our free group on one generator is by definition given by:
But, what does this mean? This means that [math]F_1[/math] is generated by a variable [math]g[/math] without relations of type [math]g^s=1[/math], between this variable and itself, preventing our group to be cyclic. We conclude that [math]F_1[/math] is the usual group formed by the integers:
Thus the associated Cayley graph is the usual [math]\mathbb Z[/math] graph, that we know well from the previous chapters, with edges drawn between the neighbors:
Here we have used, as before, a solid circle for the root. Now this being obviously the unique rooted tree having valence [math]2[/math] everywhere, we are done with the [math]N=1[/math] case.
(2) At [math]N=2[/math] now, our free group on two generators is by definition given by:
So, question now, what does this mean? This means, by definition, that [math]F_2[/math] is generated by two variables [math]g,h[/math], without relations between them. In other words, our generators [math]g,h[/math] are as free as possible, in the sense that the following must be satisfied:
Which is of course something a bit abstract, and dealing with all these conditions does not look like an easy task. However, after some thinking, this is in fact something very simple, because we can list the group elements, according to their length, as follows:
Observe that we have one element of length 0, namely the unit 1, then 4 elements of length 1, then [math]16-4=12[/math] elements of length 2, then [math]64-16=48[/math] elements of length 3, and so on. Now when drawing the Cayley graph, the picture is as follows, with the convention that the graph goes on, in a 4-valent way, in each possible direction:
But this graph being obviously the unique infinite rooted tree having valence [math]4[/math] everywhere, we are done with the [math]N=2[/math] case too.
(3) At [math]N=3[/math] now, our free group on 3 generators is by definition given by:
As before at [math]N=2[/math], this is something a bit abstract, but we can list the group elements according to their length, and this provides us with some understanding, on what our group [math]F_3[/math] exactly is. And then, when drawing the Cayley graph, we are again in a situation which is similar to the one at [math]N=2[/math], but this time with our graph being [math]6[/math]-valent everywhere, and more specifically, being the unique 6-valent rooted tree:
(4) At an arbitrary [math]N\in\mathbb N[/math] now, the situation is quite similar to what we have seen in the above at [math]N=1,2,3[/math], and this leads to the conclusion in the statement.
Many other things can be said about free groups, and other free products of groups, and their Cayley graphs. We will be back to these topics on several occasions, first at the end of the present chapter, with a discussion of the random walks on the above snowflake graphs, then in chapter 7 below, with a key occurrence of [math]F_N[/math] in topology, and then on a more systematic basis when doing groups, starting from chapter 9 below.
6b. Counting, Cayley
Moving ahead, let us discuss now counting questions for trees. We already talked a bit about counting questions for various types of graphs before, but in the case of the trees, many interesting things can be said, that we will explore in what follows.
We are mainly interested in counting the trees having [math]N[/math] vertices. However, this is something quite tricky, and it is better instead to try to count the tree with vertices labeled [math]1,\ldots,N[/math]. And, regarding these latter trees, we have the following key fact:
To any tree with vertices labeled [math]1,\ldots,N[/math] we can associate its Pr\"ufer sequence, [math](a_1,\ldots,a_{N-2})[/math] with [math]a_i\in\{1,\ldots,N\}[/math], constructed as follows:
- At step [math]i[/math], remove the leaf with the smallest label,
- Add the label of that leaf's neighbor to your list,
- And stop when you have only [math]2[/math] vertices left.
This is something quite self-explanatory, and as an illustration for how the Pr\"ufer encoding works, consider for instance the following tree:
So, let us see how the algorithm works for this tree. The details are as follows:
-- Following the algorithm, we first have to remove 1, and put 4 on our list.
-- Then we have to remove 2, and then 3 too, again by putting 4 on our list, twice.
-- Then, when left with [math]4,5,6[/math], we have to remove 4, and put 5 on our list.
-- And with this we are done, because we have only 2 vertices left, so we stop.
As a conclusion to this, for the above tree the Pr\"ufer sequence is as follows:
So, this is how the Pr\"ufer encoding works, and feel free to work out some more examples, on your own. Quite remarkably, we have as well an inverse algorithm, as follows:
To any Pr\"ufer sequence, [math](a_1,\ldots,a_{N-2})[/math] with [math]a_i\in\{1,\ldots,N\}[/math], we can associate a tree with vertices labeled [math]1,\ldots,N[/math], as follows:
- Start with vertices [math]1,\ldots,N[/math], and declare the valence of [math]i\in\{1,\ldots,N\}[/math] to be the number of times [math]i[/math] appears in the Pr\"ufer sequence, plus [math]1[/math],
- Read the Pr\"ufer sequence, and for any number on it [math]i\in\{1,\ldots,N\}[/math], connect [math]i[/math] to the smallest vertex [math]j[/math] having valence [math]1[/math], and lower by one the valences of [math]i,j[/math],
- At the end, you will have two vertices left of valence [math]1[/math]. Connect them.
Again, this is something quite self-explanatory, and as an illustration for how this works, consider the following Pr\"ufer sequence, that we already know from before:
So, let us see how the algorithm works for this sequence. The details are as follows:
-- Following the algorithm, we start with vertices, with valences, as follows:
-- Then we read the Pr\"ufer sequence, as indicated. The first occurrence of 4 will lead to an edge [math]1-4[/math], then the second occurrence of 4 will lead to an edge [math]2-4[/math], and then the third occurrence of 4 will lead to an edge [math]3-4[/math]. Thus, at this point of the algorithm, the sequence of vertices, with valences, and some edges added, will look as follows:
-- We keep reading the Pr\"ufer sequence, by reading the last number there, the 5 at the end. This will produce an edge [math]4-5[/math], so our updated graph in the making becomes:
-- Thus, bulk of the algorithm executed, and what we have now is what is indicated above, namely a graph, save for two valence 1 vertices, which are still to be connected. By connecting these two vertices, with an edge [math]5-6[/math], our graph becomes:
And good news, this is indeed a tree. And as further good news, this is in fact a tree that we know from before, having [math]p=(4,4,4,5)[/math] as Pr\"ufer sequence, namely:
Very nice all this, and, obviously, it looks like we are close to a big discovery. So, let us formulate now our main theorem, inspired from the above:
The trees with vertices labeled [math]1,\ldots,N[/math] are bijectively encoded by their Pr\"ufer sequences, [math](a_1,\ldots,a_{N-2})[/math] with [math]a_i\in\{1,\ldots,N\}[/math], constructed as follows:
- At step [math]i[/math], remove the leaf with the smallest label,
- Add the label of that leaf's neighbor to your list,
- And stop when you have only [math]2[/math] vertices left.
This follows from the above, and from some more thinking, as follows:
(1) To start with, what we have in the statement is a copy of Definition 6.5, that is, of the Pr\"ufer encoding algorithm, along with claim that this algorithm is bijective.
(2) In order to prove the bijectivity, we will use the Pr\"ufer decoding algorithm, from Definition 6.6. We have already seen in the above that these algorithms are inverse to each other, for a certain tree and sequence, and the claim is that this holds in general.
(3) In order to verify this claim, nothing better than checking it first for some sort of “random tree”. So, let us pick our favorite example of tree, that we used many times in the beginning of this chapter, and label its vertices in a somewhat random way:
(4) The associated Pr\"ufer sequence is then easy to compute, and is given by:
(5) Now let us compute the tree associated to this Pr\"ufer sequence. We follow here the algorithm in Definition 6.6, by starting with vertices, with valences, as follows:
We read now the Pr\"ufer sequence, and perform the operations in Definition 6.6. To start with, after reading the entries [math]13,10,13,13,14,15[/math], our picture becomes:
Then, after reading the next entries [math]5,15,11[/math], our picture becomes:
Then, after reading the next entry, which is an [math]11[/math], our picture becomes:
The next entry is a 14, and changing our graphics, our picture becomes:
The next entries are [math]15,6,3[/math], and after reading them, our picture becomes:
The last two entries are [math]14,10[/math], and after reading them, our picture becomes:
It remains to connect the remaining 2 vertices, and we get what we want, namely:
(6) Summarizing, good work that we did here, and with our theorem proved for this beast, I would say that the confidence rate for our theorem jumps to a hefty [math]99\%[/math]. As for the remaining [math]1\%[/math], I will leave this to you, as an instructive exercise. And with the comment that we will come back to this, later, with some alternative methods too.
As a first consequence of Theorem 6.7, we have the following famous formula:
The number of trees with vertices labeled [math]1,\ldots,N[/math] is
This is clear from the bijection in Theorem 6.7, because the number of possible Pr\"ufer sequences, [math](a_1,\ldots,a_{N-2})[/math] with [math]a_i\in\{1,\ldots,N\}[/math], that is, sequences obtained by picking [math]N-2[/math] times numbers from [math]\{1,\ldots,N\}[/math], is obviously [math]T_N=N^{N-2}[/math].
As a number of comments, however, which have to be made here, we have:
(1) First of all, in order to avoid confusions, what we just counted are trees up to obvious isomorphism. For instance at [math]N=2[/math] we only have 1 tree, namely:
Indeed, the other possible tree, namely [math]2-1[/math], is clearly isomorphic to it.
(2) At [math]N=3[/math] now, the trees are sequences of type [math]a-b-c[/math], with [math]\{a,b,c\}=\{1,2,3\}[/math]. Now since such a tree is uniquely determined, up to graph isomorphism, by the middle vertex [math]b[/math], we have 3 exactly trees up to isomorphism, namely:
(3) At [math]N=4[/math], we first have [math]2\binom{4}{2}=12[/math] bivalent trees, which can be listed by choosing the ordered outer vertices, and putting the smallest label left at position [math]\#2[/math]:
And then, for completing the count, we have [math]\binom{4}{1}=4[/math] trees with a trivalent vertex, which again, by using some sort of lexicographic order, look as follows:
(4) And so on, and it is actually instructive here to try yourself listing the [math]5^3=125[/math] trees at [math]N=5[/math], in order to convince you that the Cayley formula is something quite subtle, hiding inside plenty of binomials and factorials.
(5) Which leads us to the question, what is the simplest proof of the Cayley formula. Well, there are many possible proofs here, for all tastes, with the above one, using Pr\"ufer sequences, being probably the simplest one. We will present as well a second proof, a bit later, due to Kirchoff, which is based on linear algebra, and is non-trivial as well.
Moving ahead, as a more specialized consequence of Theorem 6.7, we have:
The number of trees with vertices labeled [math]1,\ldots,N[/math], having respective valences [math]v_1,\ldots,v_N[/math], is the multinomial coefficient
This follows again from Theorem 6.7, the idea being as follows:
(1) As a first observation, the formula in the statement makes sense indeed, with what we have there being indeed a multinomial coefficient, and this because by using the fact that the number of edges is [math]E=N-1[/math], that we know from Proposition 6.3, we have:
(2) In what regards now the proof, this follows from Theorem 6.7, the point being that in the Pr\"ufer sequence, each number [math]i\in\{1,\ldots,N\}[/math] appears exactly [math]v_i-1[/math] times.
(3) As for the last assertion, this comes from this, and the multinomial formula:
Thus, we are led to the conclusions in the statement.
6c. Kirchoff formula
We discuss in this section another proof of the Cayley formula, this time due to Kirchoff, by using linear algebra techniques, of analytic flavor. As a bonus, we will see that the main result of Kirchoff goes well beyond what the Cayley formula says.
The Kirchoff approach is based on the following simple observations:
The following happen:
- Any connected graph has a spanning tree, meaning a tree subgraph, making use of all vertices.
- For the complete graph [math]K_N[/math], with vertices labeled [math]1,\ldots,N[/math], the spanning trees are exactly the trees with vertices labeled [math]1,\ldots,N[/math].
Both the assertions are trivial, the idea being as follows:
(1) The fact that any connected graph has indeed a spanning tree is something which is very intuitive, clear on pictures, and we will leave the formal proof, which is not difficult, as an exercise. As an illustration for this, here is a picture of a quite random graph, which, after removal of some of the edges, the dotted ones, becomes indeed a tree:
(2) As for the second assertion, this is something which is clear too, and again we will leave the formal proof, which is not difficult at all, as an exercise.
In view of the above, the following interesting question appears: \begin{question} Given a connected graph [math]X[/math], with vertices labeled [math]1,\ldots,N[/math], how to count its spanning trees? And, for the complete graph [math]K_N[/math], do we really get [math]N^{N-2}[/math] such spanning trees, in agreement with the Cayley formula, by using this method? \end{question} So, hope you get the point, we are trying here to do what was advertised in the above, namely new proof of the Cayley formula, plus more. Getting to work now, following Kirchoff, the idea will be that of connecting the spanning trees of a connected graph [math]X[/math] to the combinatorics of the Laplacian of [math]X[/math], given by the following formula:
We have already seen many things in chapter 5, regarding [math]L[/math], and in order to get started, we will just need the fact, that we know well, and which is trivial, that [math]L[/math] is bistochastic, with zero row and column sums. Indeed, this makes the link with the following basic linear algebra fact, that we can use afterwards, for our Laplacian [math]L[/math]:
For a matrix [math]L\in M_N(\mathbb R)[/math] which is bistochastic, with zero row and column sums, the signed minors
This is something very standard, the idea being as follows:
(1) Before anything, let us do a quick check at [math]N=2[/math]. Here the bistochastic matrices, with zero row and column sums, are as follows, with [math]a\in\mathbb R[/math]:
But this gives the result, with the number in question being [math]T_{ij}=a[/math].
(2) Let us do as well a quick check at [math]N=3[/math]. Here the bistochastic matrices, with zero row and column sums, are as follows, with [math]a,b,c,d\in\mathbb R[/math]:
But this gives again the result, with the number in question being [math]T_{ij}=ad-bc[/math].
(3) In the general case now, where [math]N\in\mathbb N[/math] is arbitrary, the bistochastic matrices with zero row and column sums are as follows, with [math]A\in M_n(\mathbb R)[/math] with [math]n=N-1[/math] being an arbitary matrix, and with [math]R_1,\ldots,R_n[/math] and [math]C_1,\ldots,C_n[/math] being the row and column sums of this matrix, and [math]S=\sum R_i=\sum C_i[/math] being the total sum of this matrix:
We want to prove that the signed minors of [math]L[/math] coincide, and by using the symmetries of the problem, it is enough to prove that the following equality holds:
But, what we have on the right is [math]-\det A[/math], and what we have on the left is:
Thus, we are led to the conclusion in the statement.
We can now formulate, following Kirchoff, the following key result:
Given a connected graph [math]X[/math], with vertices labeled [math]1,\ldots,N[/math], the number of spanning trees inside [math]X[/math], meaning tree subgraphs using all vertices, is
This is something non-trivial, the idea being as follows:
(1) We know from Proposition 6.12 that the signed minors of [math]L[/math] coincide. In other words, we have a common formula as follows, with [math]T\in\mathbb Z[/math] being a certain number:
Our claim, which will prove the result, is that the number of spanning trees [math]T_X[/math] is precisely this common number [math]T[/math]. That is, with [math]i=j=1[/math], our claim is that we have:
(2) In order to prove our claim, which is non-trivial, we use a trick. We orient all the edges [math]e=(ij)[/math] of our graph as to have [math]i \lt j[/math], and we define the ordered incidence matrix of our graph, which is a rectangular matrix, with the vertices [math]i[/math] as row indices, and the oriented edges [math]e=(ij)[/math] as column indices, by the following formula:
The point is that, in terms of this matrix, the Laplacian decomposes as follows:
(3) Indeed, let us compute the matrix on the right. We have, by definition:
Let us first compute the contributions of type [math]1\times1[/math], to the above sum. These come from the edges [math]e[/math] having the property [math]E_{ie}=E_{je}=1[/math]. But [math]E_{ie}=1[/math] means [math]e=(ik)[/math] with [math]i \lt k[/math], and [math]E_{je}=1[/math] means [math]e=(jl)[/math] with [math]j \lt l[/math]. Thus, our condition [math]E_{ie}=E_{je}=1[/math] means [math]i=j[/math], and [math]e=(ik)[/math] with [math]i \lt k[/math], so the contributions of type [math]1\times1[/math] are given by:
Similarly, the contributions of type [math](-1)\times(-1)[/math] to our sum come from the equations [math]E_{ie}=E_{je}=-1[/math], which read [math]i=j[/math] and [math]e=(ki)[/math] with [math]k \lt i[/math], so are given by:
Now observe that by summing, the total [math]1[/math] contributions to our sum, be them of type [math]1\times1[/math] or [math](-1)\times(-1)[/math], are given by the following formula, [math]v[/math] being the valence function:
(4) It remains to compute the total [math]-1[/math] contributions to our sum. But here, we first have the contributions of type [math]1\times(-1)[/math], coming from the equations [math]E_{ie}=1,E_{je}=-1[/math]. Now since [math]E_{ie}=1[/math] means [math]e=(ik)[/math] with [math]i \lt k[/math], and [math]E_{je}=-1[/math] means [math]e=(lj)[/math] with [math]l \lt j[/math], our equations [math]E_{ie}=1,E_{je}=-1[/math] amount in saying that [math]e=(ij)[/math] with [math]i \lt j[/math]. We conclude that the contributions of type [math](-1)\times1[/math] to our sum are given by:
Similarly, the contributions of type [math](-1)\times1[/math] to our sum come from the equations [math]E_{ie}=-1,E_{je}=1[/math], which read [math]e=(ij)[/math] with [math]i \lt j[/math], so these are given by:
Now by summing, the total [math]-1[/math] contributions to our sum, be them of type [math]1\times(-1)[/math] or [math](-1)\times1[/math], are given by the following formula, [math]d[/math] being the adjacency matrix:
(5) But with this, we can now finish the proof of our claim in (2), as follows:
Thus, we have [math]EE^t=L[/math], and claim proved. Note in passing that our formula [math]EE^t=L[/math] gives another proof of the property [math]L\geq0[/math], that we know from chapter 5.
(6) Getting now towards minors, if we denote by [math]F[/math] the submatrix of [math]E[/math] obtained by deleting the first row, the one coming from the vertex 1, we have, for any [math]i,j \gt 1[/math]:
We conclude that we have the following equality of matrices:
(7) The point now is that, in order to compute the determinant of this latter matrix, we can use the Cauchy-Binet formula from linear algebra. To be more precise, Cauchy-Binet says that given rectangular matrices [math]A,B[/math], of respective sizes [math]M\times N[/math] and [math]N\times M[/math], we have the following formula, with [math]A_S,B_S[/math] being both [math]M\times M[/math] matrices, obtained from [math]A,B[/math] by cutting, in the obvious way, with respect to the set of indices [math]S[/math]:
Observe that this formula tells us at [math]M \gt N[/math] that we have [math]\det(AB)=0[/math], as it should be, and at [math]M=N[/math] that we have [math]\det(AB)=\det A\det B[/math], again as it should be. At [math]M \lt N[/math], which is the interesting case, the Cauchy-Binet formula holds indeed, with the proof being a bit similar to that of the formula [math]\det(AB)=\det A\det B[/math] for the square matrices, which itself is not exactly a trivial business. For more on all this, details of the proof, examples, and other comments, we refer to any advanced linear algebra book.
(8) Now back to our questions, in the context of our formula [math]L^{11}=FF^t[/math] from (6), we can apply Cauchy-Binet to the matrices [math]A=F[/math] and [math]B=F^t[/math], having respective sizes [math](N-1)\times N[/math] and [math]N\times(N-1)[/math]. We are led in this way to the following formula, with [math]S[/math] ranging over the subsets of the edge set having size [math]N-1[/math], and with [math]F_S[/math] being the corresponding square submatrix of [math]E[/math], having size [math](N-1)\times(N-1)[/math], obtained by restricting the attention to the columns indexed by the subset [math]S[/math]:
(9) Now comes the combinatorics. The sets [math]S[/math] appearing in the above computation specify in fact [math]N-1[/math] edges of our graph, and so specify a certain subgraph [math]X_S[/math]. But, in this picture, our claim is that we have the following formula:
Indeed, since the subgraph [math]X_S[/math] has [math]N[/math] vertices and [math]N-1[/math] edges, it must be either a spanning tree, or have a cycle, and the study here goes as follows:
-- In the case where [math]X_S[/math] is a spanning tree, we pick a leaf of this tree, in theory I mean, by leaving it there, on the tree. The corresponding row of [math]F_S[/math] consists then of a [math]\pm1[/math] entry, at the neighbor of the leaf, and of [math]0[/math] entries elsewhere. Thus, by developing [math]\det(F_S)[/math] over that row, we are led to a recurrence, which gives [math]\det(F_S)=\pm1[/math], as claimed above.
-- In the other case, where [math]X_S[/math] has a cycle, the sum of the columns of [math]F_S[/math] indexed by the vertices belonging to this cycle must be [math]0[/math]. We conclude that in this case we have [math]\det(F_S)=0[/math], again as claimed above, and this finishes the proof of our claim.
(10) By putting now everything together, we obtain the following formula:
Thus, we are led to the conclusions in the statement.
As a basic application of the Kirchoff formula, let us apply it to the complete graph [math]K_N[/math]. We are led in this way to another proof of the Cayley formula, as follows:
The number of spanning trees of the complete graph [math]K_N[/math] is
This is something which is clear from the Kirchoff formula, but let us prove this slowly, as an illustration for the various computations above:
(1) At [math]N=2[/math] the Laplacian of the segment [math]K_2[/math] is given by the following fomula:
Thus the common cofactor is 1, which equals the number of spanning trees, [math]2^0=1[/math].
(2) At [math]N=3[/math] the Laplacian of the triangle [math]K_3[/math] is given by the following fomula:
Thus the common cofactor is 3, which equals the number of spanning trees, [math]3^1=3[/math].
(3) At [math]N=4[/math] the Laplacian of the tetrahedron [math]K_4[/math] is given by the following fomula:
Here the cofactor is [math]27-11=16[/math], which is the number of spanning trees, [math]4^2=16[/math].
(4) In general, for the complete graph [math]K_N[/math], the Laplacian is as follows:
Thus, the common cofactor is [math]N^{N-2}[/math], in agreement with the Cayley formula.
Very nice all this, so we have now a good understanding of the Cayley formula. However, the story is not over here, because in what regards the counting of trees having [math]N[/math] vertices, this time without labeled vertices, things are far more complicated, and there is no formula available, for the number of such trees. We refer here to the literature.
6d. More Kirchoff
Our purpose now will be to further build on Theorem 6.13, with an analytic interpretation of the quantity [math]T_X=(-1)^{i+j}\det(L^{ij})[/math] found there. So, let us first go back to the general setting of Proposition 6.12. As a continuation of the material there, we have:
For a matrix [math]L\in M_N(\mathbb R)[/math] which is bistochastic, with zero row and column sums, we have, independently of the chosen indices [math]i,j[/math],
This is something quite standard, the idea being as follows:
(1) To start with, since our matrix [math]L[/math] is bistochastic, with zero sums, 0 is indeed an eigenvalue of it, with the all-one vector as eigenvector, so our statement makes indeed sense. Observe also that, according to Proposition 6.12, the numbers [math](-1)^{i+j}\det(L^{ij})[/math] in the statement do not depend on the choice of the chosen indices [math]i,j[/math].
(2) In order to see what is going on, let us do a quick check at [math]N=2[/math]. Here the bistochastic matrices, with zero row and column sums, are as follows, with [math]a\in\mathbb R[/math]:
The eigenvalues are then [math]0,2a[/math], and the formula in the statement holds indeed, as:
(3) Let us do as well a quick check at [math]N=3[/math]. Here the bistochastic matrices, with zero row and column sums, are as follows, with [math]a,b,c,d\in\mathbb R[/math]:
Thus, good news, time for some Sarrus, which gives, after 5 minutes or so:
But [math]\det(x-L)=x(x-\lambda_1)(x-\lambda_2)[/math], so our formula holds again, as:
(4) In the general case now, where [math]N\in\mathbb N[/math] is arbitrary, let us write:
Based on this, we have the following computation, obtained by fully developing the determinant, and by using Proposition 6.12 at the end:
Thus, we are led to the formula in the statement.
The above result is quite interesting, suggesting to reformulate the Kirchoff formula from Theorem 6.13 in a more analytic way, by using the eigenvalues of [math]L[/math], as follows:
Given a connected graph [math]X[/math], with vertices labeled [math]1,\ldots,N[/math], the number of spanning trees inside [math]X[/math] is
This follows indeed by putting together Theorem 6.13 and Proposition 6.15, and with the remark that, as explained in chapter 5, for a connected graph the multiplicity of the 0 eigenvalue is 1, and so we have [math]\lambda_1,\ldots,\lambda_{N-1} \gt 0[/math], as stated.
As before with our previous version of the Kirchoff theorem, we can apply this to the complete graph, and we are led to yet another proof of the Cayley formula, as follows:
The number of spanning trees of the complete graph [math]K_N[/math] is
We know from chapter 2 that the adjacency matrix of [math]K_N[/math] diagonalizes as follows, with [math]F_N=(w^{ij})[/math] with [math]w=e^{2\pi i/N}[/math] being as usual the Fourier matrix:
We deduce from this that the corresponding Laplacian matrix, which is given by the formula [math]L=(N-1)1_N-d[/math], diagonalizes as follows:
Now by applying Theorem 6.16, the number of spanning trees follows to be:
Thus, we are led to the conclusions in the statement.
In order to have now more examples, we have to browse through our diagonalization results from chapter 2, and afterwards, and we are led in this way into:
For a connected circulant graph with vertices labeled [math]1,\ldots,N[/math], and having valence [math]k[/math], with the corresponding adjacency matrix diagonalized as
with [math]\mu_1,\ldots,\mu_{N-1}\in\mathbb C[/math], the number of spanning trees inside [math]X[/math] is given by:
Here the formulation of the statement heavily relies on our knowledge of circulant graphs, from chapter 4. As for the result itself, this follows from Theorem 6.16, by using [math]L=(k1_n-d)[/math], and the diagonalization formula for [math]d[/math] in the statement.
As an illustration for the above result, we have:
The number of spanning trees of the circle is [math]N[/math].
As a die-hard physicist, I never use Lemmas and Corollaries in my classes or books, way too scary and mathematical, but good time now for a Corollary. Indeed, the general policy is to end each chapter in beauty, with a Theorem, but the above statement being a total triviality, as you can instantly see by contemplating the circle graph, calling it Theorem would have been inappropriate. Anyway, and regarding now the proof, based on Theorem 6.18, which is after all something quite instructive, here that is:
(1) We know from chapter 2 that the adjacency matrix of the circle [math]X[/math] diagonalizes as follows, with [math]F_N=(w^{ij})[/math] with [math]w=e^{2\pi i/N}[/math] being as usual the Fourier matrix:
(2) Now by using Theorem 6.18, and some root of unity know-how, we get:
(3) To be more precise, at the end we have used [math]x^N-1=(x-1)(x-w)\ldots(x-w^{N-1})[/math], first with [math]x=0[/math] in order to get the first needed formula, and then with [math]x=1[/math], after dividing both sides by [math]x-1[/math], in order to get the second needed formula. Thus, Corollary proved.
General references
Banica, Teo (2024). "Graphs and their symmetries". arXiv:2406.03664 [math.CO].