18 312 Algebraic Combinatorics Lionel Levine Lecture 19 Lecture date April 21 2011 1 1 1 Notes by David Witmer Matrix Tree Theorem Undirected Graphs Let G V E be a connected undirected graph with n vertices and let G be the number of spanning trees of G Definition 1 Laplacian matrix of undirected graph The Laplacian matrix L of G is equal to D A where d1 0 D 0 dn such that di is the degree of vertex i i e the number of edges incident to vertex i and A is the adjacency matrix of G such that A aij 1 if i j E aij 0 else Theorem 2 Matrix Tree Theorem Version 1 G 1 1 2 n 1 n where 1 2 n 1 are non zero eigenvalues of the Laplacian matrix L of G 1 2 Directed Graphs We can give another version of the Matrix Tree Theorem for directed graphs First we need to define spanning trees and Laplacian matrices for directed graphs Let V E be a directed graph 19 1 Definition 3 Oriented spanning tree An oriented spanning tree of rooted at r V is a spanning subgraph T V A such that 1 Every vertex v 6 r has out degree 1 2 r has out degree 0 3 T has no oriented cycles Example 4 Consider the following directed graph 1 r 4 2 3 1 r 4 2 3 1 r 4 2 3 1 r 4 2 3 It has three oriented spanning trees Definition 5 Laplacian matrix of directed graph The Laplacian matrix L of is equal to D A where d1 0 D 0 dn such that di is the out degree of vertex i i e j V i j E and A is the adjacency matrix of Theorem 6 Matrix Tree Theorem Version 2 Let r oriented spanning trees of rooted at r 19 2 and Lr be the Laplacian matrix of with the row and column corresponding to vertex r crossed out Then r det Lr where Lr is the Laplacian matrix L with row and column r removed Example 7 Consider the directed graph from the previous example Then we see that 1 r 4 2 3 2 0 D 0 0 and 0 0 A 1 1 so and 0 1 0 0 0 0 2 0 0 0 0 1 1 0 0 0 0 1 0 1 0 0 1 0 2 1 0 0 0 1 1 0 L 1 0 2 1 1 0 1 1 2 1 0 1 1 Lr 0 1 0 2 Then det Lr 2 1 2 1 1 1 3 which matches what we found in the previous example We will prove this version of the Matrix Tree Theorem and then show that it implies the version for undirected graphs Proof Reorder the vertices of so that r is the nth vertex Then det Lr d1 d2 dn 1 other terms since Lr has the di s on the diagonal and either 1 or 0 for the off diagonal 19 3 entries d1 d2 dn 1 counts the number of subgraphs H of such that each vertex v 6 r has out degree 1 So we have that H T C1 Ck where T is an oriented tree rooted at r and each Ci is an oriented cycle Then X det Lr sgn L1 1 Ln 1 n 1 Sn 1 Let fix i i i Then we have Y X Y Li i di det Lr sgn Sn 1 Q Li i i fix i fix i fix is only non zero when i i E for all i fix In this case Y Li i 1 n 1 fix i fix We wish to write X det Lr CH subgraphs H where CH is 1 if H is an oriented spanning tree and 0 otherwise Any permutation consists of fixed points and cycles A subgraph H T C1 Ck arises from if and only if the union of all cycles Ci of H contains all vertices not fixed by H which in turn is true if and only if T fix We can then conclude that X CH sgn 1 n 1 fix Sn 1 T fix Our goal is then to show that CH is 1 when H is a tree and 0 otherwise When H is a tree H T and there are no cycles Then all vertices are in fix and is the identity permutation The sign of the identity permutation is 1 and n 1 points are fixed so CH 1 Lastly we need to show that CH 0 if k 1 i e if H has a cycle For each Ci we can either choose Ci fix or Ci to be a cycle of Let i1 il be the indices of the Ci s that are formed from vertices in cycles of All other points must be fixed by so sgn 1 Ci1 1 Cil 1 This means that CH X 1 Ci1 1 Cil 1 1 Ci1 Cil i1 il k 19 4 So CH X 1 S S k k X k 1 1 k l l 0 0 if k 1 2 1 3 Proof of the Matrix Tree Theorem Version 1 Now we will show that Version 2 of the Matrix Tree Theorem implies the version for undirected graphs Proof Given undirected graph G let be the directed graph with edges i j and j i for every edge of G We first observe that there is a bijection between the set of oriented spanning trees of rooted at r and the set of spanning trees of G We can take any oriented spanning tree of rooted at r and get a spanning tree of G by disregarding the root and the orientation of the edges For any spanning tree T of G we can get an oriented spanning tree of by orienting edges along the unique path from each vertex to r Such a path exists because T is connected and is unique because T has no cycles Then n G n X r r 1 Let L be the Laplacian matrix of Then the characteristic polynomial of L is t det tI L It is true that n X det Lr 1 n 1 t t r 1 where t t is the coefficient of t in t 19 5 So we have that n G n X det Lr 1 n 1 t t r 1 n 1 1 t n Y t i where the i s are eigenvalues of L and n 0 i 1 n 1 1 n 1 1 1 n 1 1 n 1 Therefore G 2 2 1 1 n 1 n Cayley s Theorem Theorem 8 Cayley s Theorem The number of trees on n labeled vertices is nn 2 Example 9 Consider trees containing 4 vertices There are 16 44 2 total 4 of the form 1 3 2 4 and 12 of the form 1 2 3 4 Proof Any tree on n vertices is a …