Kirchhoff’s Matrix Tree Theorem for Counting Spanning Trees — A Proof for Beginners

In this post, we provide a proof of Kirchhoff’s Matrix Tree theorem [1] which is quite beautiful in our biased opinion. This is a 160-year-old theorem which connects several fundamental concepts of matrix analysis and graph theory (e.g., eigenvalues, determinants, cofactor/minor, Laplacian matrix, incidence matrix, connectedness, graphs, and trees etc.). There are already many expository articles/proof sketches/proofs of this theorem (for example, see [4-6, 8,9]). Here we compile yet-another-expository-article and present arguments in a way which should be accessible to the beginners.

Statement

Suppose  L is the Laplacian of a connected simple graph G with n vertices. Then the number of spanning trees in G, denoted by t(G), is the following:

t(G)=\frac{1}{n} \times \{ the product of all non-zero eigenvalues of L\ \}.

Continue reading “Kirchhoff’s Matrix Tree Theorem for Counting Spanning Trees — A Proof for Beginners”

Advertisements