Kirchhoff's Theorem - Kirchhoff's Theorem

Kirchhoff's Theorem

Kirchhoff's theorem relies on the notion of the Laplacian matrix of a graph that is equal to the difference between the graph's degree matrix (a diagonal matrix with vertex degrees on the diagonals) and its adjacency matrix (a (0,1)-matrix with 1's at places corresponding to entries where the vertices are adjacent and 0's otherwise).

For a given connected graph G with n labeled vertices, let λ₁, λ₂, ..., λ_n−1 be the non-zero eigenvalues of its Laplacian matrix. Then the number of spanning trees of G is

Equivalently the number of spanning trees is equal to the absolute value of any cofactor of the Laplacian matrix of G.