Counting the number of spanning trees in a graph -A spectral approachApril 29th, 2010In class we came across a metric that required us to compute the number of spanning trees of a graph. Weprovide here some discussion on how this is done (efficiently) using spectral graph theory (essentially graph theory+ linear algebra). Some of the notation and definitions are borrowed from Wikipedia’s relevant articles. We startwith some basic definitions that we will need.Definition (Spanning Tree). Given a connected undirected graph G = (V, E), a spanning tree is a subgraphH ⊆ G such that H is a tree over the entire vertex set of G.Definition (Graph Laplacian). Given an undirected graph with an ordering of its vertices (v1, v2, . . . , vn), theLaplacian matrix L (G) is defined to be a n × n matrix with the following entries:`i,j=deg (vi) if i = j−1 if viis adjacent to vj0 otherwiseThat is, the diagonal elements have values equal to the degree of the corresponding vertices, and the off-diagonalelements are -1 if an edge connects the two vertices, and 0 otherwise.The Laplacian matrix of a graph has many interesting properties. In particular, one can show that for aconnected graph, it’s Laplacian matrix has n − 1 non-zero eigen values. This is used in the following theorem.Theorem (Kirchhoff’s Matrix Tree Theorem). For a given undirected connected graph G with n vertices, letλ1, . . . , λn−1be the non-zero eigenvalues of L (G). Then, the number of distinct spanning trees of G is equal tot (G) =1nn−1Yi=1λiEquivalently, t (G) is equal to the absolute value of any cofactor of the Laplacian matrix of G.As an example, consider two examples, show in Figure 1 and Figure 2.1 234L (G) =3 −1 −1 −1−1 2 −1 0−1 −1 3 −1−1 0 −1 2λ1= 4λ2= 4λ3= 2λ4= 0t (G) =14(4)(4)(2) = 8Figure 1: Example graph, with Laplacian matrix and eigenvalues. Numbers neareach vertex indicate the chosen ordering. The total number of spanning trees can beseen to be 8 by inspection, which matches with Kirchhoff’s theorem.We will now provide some intuition as to why Kirchhoff’s theorem is correct. From spectral graph theory,we know that the Laplacian matrix of a graph G can be decomposed into the product of the incidence matrix Ewith it’s transpose:L (G) = EET112 345 6L (G) =3 −1 −1 −1 0 0−1 1 0 0 0 0−1 0 1 0 0 0−1 0 0 3 −1 −10 0 0 −1 2 −10 0 0 −1 −1 2λ1≈ 4.5646λ2= 3λ3= 1λ4= 1λ5≈ 0.4384λ6= 0t (G) =16(4.5616)(3)(1)(1)(0.4384) = 3Figure 2: 2nd example graph, with Laplacian matrix and eigenvalues. Numbers neareach vertex indicate the chosen ordering. The total number of spanning trees can beseen to be 8 by inspection, which matches with Kirchhoff’s theorem.The incidence matrix E for a graph with n nodes and m edges is a n × m matrix which indicates which edges areincident on which nodes. We as sume both the edges and nodes are given an ordering. Using the ordering of thenodes, we impose a direction on each edge such that the edge points from the lower-ordered vertex to the higherordered vertex. The entries of the incidence matrix are defined as follows:ai,j=1 if edge ejpoints out from vi−1 if edge ejpoints to vi0 otherwiseE1=1 1 1 0 0−1 0 0 1 00 −1 0 −1 10 0 −1 0 −1E2=1 1 1 0 0 0−1 0 0 0 0 00 −1 0 0 0 00 0 −1 1 1 00 0 0 −1 0 10 0 0 0 −1 −1Figure 3: Incidence matrices of the two example graphs using the same no de orderingsas before and for a fixed edge ordering. Incidence matrices resulting from other e dgeorderings would be column permutations of the display matrices.The incidence matrices for the two example graphs are shown in Figure 3. We wish to talk about the minordet (M11) of the Laplacian matrix L, i.e. the determinant of the matrix resulting from the removing the first rowand column from L. We know that L = EET, so by letting F be the matrix produced by removing the first rowfrom E, we can relate F to M11in a similar way: M11= F FT. We now utilize a theorem by Cauchy and Binet:Theorem (Cauchy-Binet formula). Let A be a m × n matrix and B be an n × m matrix. We write [n] for theset {1, 2, . . . , n} and[n]mfor all m-size subsets of [n]. For any S ∈[n]m, A[m],Sis the m × m matrix produced bytaking from A only the columns that are indexed by S. Similar notation is used for B, except instead we selectrows by index instead of columns. Then,det (AB) =XS∈([n]m)detA[m],SdetBS,[m]We will apply the Cauchy-Binet formula to the relationship M11= F FT. Thus, we havedet (M11) =XSdet (FS) detFTS=XSdet (FS)22Note here that M11is of size (n − 1) × (n − 1), so S is chosen over n − 1 sized subsets of {2, 3, . . . , m}, andthus S specifies n − 1 columns of F that constitute FS. We can think of this subset S as all possible choicesof n − 1 edges. As all trees have n − 1 edges, each choice of S could map to a choice of a spanning tree. We’dlike to decide which of these choices of S represent spanning trees, and which do not. Fortunately, there is arelationship between the determinant of FSand exactly this. We claim (without proof) that det (FS) is equalto -1 or 1 if and only if the edges specified by S induce a spanning tree , and the determinant is equal to 0 iff Sdoes not. Thus, det (FS)2becomes an indicator variable for a choice of S which takes the value 1 if S induces aspanning tree, and 0 otherwise. The right-hand summation of the above equation therefore is a count of the totalnumber of spanning trees, which (by the Cauchy-Binet formala) is equivalent to minor det (M11). Our argumentis symmetric for other selected minors (say an arbitrary minor det (Mij).Thus we have that the determinant of a minor of of L (G) is equal to the number of spanning tree s. There isa result (although I’m not sure where it is to reference it) that shows equivalence between the these minors andthe alternative