# Matrix tree theorem

A degree matrix ${\displaystyle D}$ 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: ${\displaystyle L=D-A}$, where ${\displaystyle A}$ is the adjacency matrix, and ${\displaystyle D}$ is the degree matrix.
Matrix tree theorem states, the determinant of a matrix, obtained by deleting the ${\displaystyle k}$-th row and column from the graph's Laplacian is independent from the choice of ${\displaystyle k}$, and is equal to the number of spanning trees of the graph.