Matrix Tree Theorem Explained with Worked Examples

The matrix-tree theorem says the number of spanning trees of a connected graph equals any cofactor of its Laplacian matrix , where holds the vertex degrees and is the adjacency matrix.

Write 2x or 2*x to multiply, ^ for powers, and ; between simultaneous equations. You can also type factor, expand, derivative of, integrate … from a to b, limit … as x->0 or 15% of 80.

Try an example

Before you start

What Matrix tree theorem (Kirchhoff) means

Delete one row and the matching column of the Laplacian and take the determinant (or 3 × 3 determinant) of what remains. The result counts the ways to join all the vertices with no cycles.

For the complete graph on vertices the answer is (Cayley’s formula). The theorem turns a counting problem about graphs into a determinant, which is an efficient calculation.

The eigenvalues of the Laplacian give another form: the count is the product of the non-zero eigenvalues divided by , connecting to the characteristic equation and to Perron–Frobenius ideas for networks.

What is it used for?

The matrix-tree theorem counts the spanning trees of a graph with a determinant, avoiding the need to list them all.

How to use matrix tree theorem (kirchhoff)

  1. Write the Laplacian .
  2. Delete the last row and column.
  3. Take the determinant.
  4. That number is the count of spanning trees.

Graph

A triangle graph has three spanning treesABC-0.500.511.522.533.5-0.500.511.522.53A triangle graph has three spanning treesxyGraph with x from -0.5 to 3.5 and y from -0.5 to 3. Shows triangle graph (4); point A at (0.5, 0.5); point B at (2.5, 0.5); point C at (1.5, 2.2).

Remove any one of the three edges and the other two form a spanning tree, giving 3.

Worked examples

These examples are worked by hand, step by step, so you can compare your own working.

Example 1: a triangle

Count the spanning trees of the triangle .

Worked example
Answer
33
  1. Laplacian
  2. Delete the last row and column
  3. Determinant

Example 2: a path

Count the spanning trees of a path on 3 vertices.

Worked example
Answer
11
  1. Laplacian
  2. Delete the last row and column
  3. Determinant

Example 3: K₄

Count the spanning trees of the complete graph on 4 vertices.

Worked example
Answer
16=4216=4^{2}
  1. 3 × 3 minor
  2. Determinant

Special cases

A few situations come up again and again. Knowing them saves time and helps you spot answers that cannot be right.

triangle K₃

delete row/col 1: det(2 −1; −1 2)

3.

K₄

Cayley 4²

16.

K₅

5³

125.

cycle C₄

spanning trees = 4

4.

Word problems

The number of spanning trees equals any cofactor of the Laplacian L = D − A. For the complete graph Kₙ it is nⁿ⁻² (Cayley).

K₃

Reduced Laplacian (2 −1; −1 2).

  1. 4 − 1
  2. Check: ✓3

K₄

4².

  1. 16
  2. Check: ✓16

K₅ Higher

5³.

  1. 125
  2. Check: ✓125

C₄ Higher

Remove one of the four edges.

  1. 4
  2. Check: ✓4

Common mistakes

Using the adjacency matrix alone

A ✗

L = D − A ✓

Laplacian.

Full determinant

det L ✗

det L = 0, take a cofactor ✓

Singular.

Only complete graphs

complete only ✗

any connected graph ✓

General.

Counting labelled spanning trees as unlabelled

wrong ✗

labelled ✓

Distinct edge sets.

Exam tips

  1. L = D − A.
  2. Delete a row and column.
  3. Take the determinant.
  4. Kₙ: nⁿ⁻².
  5. det L = 0 always.

Practice questions

Try each one on paper, then open the answer. Use the solver above to see the full working.

1. Spanning trees of K₆ Foundation

1296

2. Spanning trees of K₃ Foundation

3

3. Spanning trees of a path on 5 vertices Foundation

1

4. Spanning trees of C₅ Higher

5

5. Spanning trees of K₇ Higher

16807

6. Edges in a spanning tree of K₆ Higher

5

Practice generator

Unlimited fresh questions with instant marking. Choose a level, work it out on paper, then type your answer.

Solve: …

Key terms

Matrix-tree theorem
Spanning trees from a cofactor.
Laplacian
D − A.
Spanning tree
Tree on all vertices.
Cofactor
Signed minor.
Adjacency matrix
A.
Degree matrix
D.

Frequently asked questions

What does the matrix-tree theorem say?

The number of spanning trees is any cofactor of the Laplacian.

What is the Laplacian?

D − A.

How many spanning trees does Kₙ have?

nⁿ⁻².

What is det L?

Always 0.

Which page covers determinants?

determinant of a 3 × 3 matrix.

Which page covers Perron–Frobenius?

Perron–Frobenius theorem.

More in Vectors and matrices and the formula sheets.