#21. Counting Spanning Trees

(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! 🤯