#21. Counting Spanning Trees
(Back to course page.)
Link to Slides · Link to recording: Part 1 and Part 2
Prompts for discussion:
We spent time on the determinant of the Laplacian of a graph here (short of one vertex). Is there a structural interpretation of the determinant of the adjacency matrix? There are some thoughts here.
Graham and Pollak showed that the determinant of the distance matrix of a tree T on n vertices - the n \times n matrix whose each (v, w) \in V(T) \times V(T) entry is the ordinary graph distance between v and w-depends only on n. In fact, they gave a formula: -(n-1)(-2)^{n-2}. I thought this was really neat: the determinant seems to be completely independent of the structure of the tree! 🤯
