# Matrix tree theorem

From Algorithmist

**Matrix tree theorem** provides a connection between the number of spanning trees of a graph and graph's Laplacian matrix.

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.

## References[edit]

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