Steven Klee, Matthew T. Stamps
Published 2019-03-12Version 1
Kirchhoff's Matrix-Tree Theorem asserts that the number of spanning trees in a finite graph can be computed from the determinant of any of its reduced Laplacian matrices. In many cases, even for well-studied families of graphs, this can be computationally or algebraically taxing. We show how two well-known results from linear algebra, the Matrix Determinant Lemma and the Schur complement, can be used to elegantly count the spanning trees in several significant families of graphs.
Comments: This paper presents unweighted versions of the results in arXiv:1903.03575 with more concrete and concise proofs. It is intended for a broad audience and has extra emphasis on exposition. It will appear in the American Mathematical Monthly
Homomorphisms of Strongly Regular Graphs
Linear algebraic techniques for weighted spanning tree enumeration
Positive discrepancy, MaxCut, and eigenvalues of graphs
![QR code for arXiv:1903.04973 [math.CO]](http://oss.arxitics.com/images/favicon.svg)