#21. Counting Spanning Trees

Published

28 Nov, 2023

(Back to course page.)

Link to Slides · Link to recording: Part 1 and Part 2

Prompts for discussion:

  1. 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.

  2. 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! 🤯