Joint Graduate Student Colloquium

Zack Cramer, Pure Mathematics Department, University of Waterloo

"The Matrix-Tree Theorem"

The matrix-tree theorem states that the number of spanning trees of a graph can be computed as the determinant of a certain matrix derived from the graph. We will showcase an elementary proof that arises as an application of the Cauchy-Binet theorem, an elegant result from linear algebra that generalizes the multiplicative property of the determinant. Finally, we will state an interesting reformulation of the matrix-tree theorem and examine some quick applications in graph theory.

MC 2035