Skip to content
Tutorials Center
My learning

Topics

Lesson 18 of 36 Β· Trees and Spanning Trees

The Matrix-Tree Theorem

Count the spanning trees of any graph with a determinant: build the Laplacian matrix, apply Kirchhoff's matrix-tree theorem, and check it against Cayley's formula and brute force in Python.

How many different spanning trees does a graph have? For a small graph you can list them, but the number explodes: the complete graph K_10 has 100 million. In 1847 Gustav Kirchhoff, studying electrical circuits, discovered that the count is a determinant. This is the matrix-tree theorem, a bridge between combinatorics and linear algebra, and our first taste of what the Laplacian matrix can do.

The Laplacian matrix

For a simple graph with vertices 1..n, the Laplacian is L = D βˆ’ A, where D is the diagonal matrix of degrees and A is the adjacency matrix. Concretely:

  • L[i][i] = deg(i),
  • L[i][j] = βˆ’1 if i and j are adjacent, and 0 otherwise.

Every row and column of L sums to zero. Remember the product D Dα΅€ from incidence matrices: it is exactly this matrix.

Python Build the Laplacian

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The determinant of L is always 0, precisely because the rows sum to zero. The interesting number appears when you delete one row and one column.

Kirchhoff's theorem

Matrix-tree theorem. The number of spanning trees of a connected graph equals any cofactor of its Laplacian: delete one row i and the same column i and take the determinant of the remaining (n-1) Γ— (n-1) matrix.

The result does not depend on which vertex you delete. A second formulation uses the eigenvalues 0 = λ₁ ≀ Ξ»β‚‚ ≀ ... ≀ Ξ»β‚™ of L: the number of spanning trees is (Ξ»β‚‚ Β· λ₃ β‹― Ξ»β‚™) / n. We study the eigenvalues of L more in the spectral chapter of the track.

Python Counting spanning trees by a cofactor

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The triangle with a tail has 3 spanning trees: you must keep the tail edge (it is a bridge) and remove one of the triangle's three edges.

Checking against brute force

We can verify the theorem by listing all (n - 1)-edge subsets and testing which are trees:

Python Matrix-tree theorem versus brute force

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Both columns agree even though the brute force examines hundreds of subsets while the determinant is a single cheap computation.

Cayley's formula, again

For the complete graph K_n, the Laplacian is nI βˆ’ J (where J is all ones). Deleting a row and column leaves nI βˆ’ J of size n βˆ’ 1, whose determinant works out to n^(nβˆ’2). That is Cayley's formula, now obtained from linear algebra instead of PrΓΌfer codes. Check it numerically, and use sympy for exact arithmetic with big numbers:

Python Cayley's formula from the determinant

Press Run (or Ctrl + Enter) to see the result here.

Program input Β· what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Weighted version and applications

If each edge has a weight (say, a conductance), the same cofactor of the weighted Laplacian gives the sum over all spanning trees of the product of their edge weights. This counts weighted spanning trees and, for an electrical network, determines effective resistances. Spanning-tree counts also measure how reliable a network is, since more spanning trees means more ways to keep it connected, and they appear in statistical physics and random walk theory (uniform random spanning trees).

Check your understanding

Quick check Β· 4 questions

of 4 answered You scored / 4 Β· perfect!

  1. 1. What is the Laplacian matrix of a simple graph?

    L = D - A: the diagonal holds degrees, off-diagonal entries are -1 for edges.
  2. 2. What does the matrix-tree theorem compute?

    Any cofactor of the Laplacian equals the number of spanning trees.
  3. 3. The determinant of the full Laplacian L is always:

    Rows of L sum to zero, so the rows are linearly dependent and det(L) = 0.
  4. 4. A connected graph is a tree. How many spanning trees does it have?

    A tree has no cycle to break, so the only spanning tree is the tree itself.

Summary

  • The Laplacian is L = D βˆ’ A; its rows sum to zero, so det(L) = 0.
  • Matrix-tree theorem: delete any row and the matching column; the determinant of what is left counts spanning trees.
  • Equivalently, the product of the nonzero eigenvalues divided by n.
  • For K_n this gives Cayley's n^(nβˆ’2).
  • A weighted Laplacian counts spanning trees by total product of weights.

Next: Graph Coloring Basics