Matrix tree theorem
A degree matrix of an undirected graph is a square matrix, which contains the sequence of degrees of graph's vertices on its diagonal, and zeroes elsewhere.
A Laplacian of a graph is defined as: , where is the adjacency matrix, and is the degree matrix.
Matrix tree theorem states, the determinant of a matrix, obtained by deleting the -th row and column from the graph's Laplacian is independent from the choice of , and is equal to the number of spanning trees of the graph.
- D.B. West. Introduction to graph theory. Prentice-Hall, 1996. Chapter 2.2.
- Godsil C., Royle G. Algebraic graph theory. Springer-Verlag, 2001. Chapter 13.2.