I don't understand how Kirchhoff's Theorem can be true

Question

Kirchhoff's Matrix-Tree theorem states that the number of spanning trees of a graph G is equal to any cofactor of its Laplacian matrix.

Wouldn't this imply that all cofactors of a Laplacian matrix must be the same, as otherwise we could get a different number of spanning trees for the same graph depending on which cofactor we took?

But that's not necessarily the case. Example:

Consider the simple, undirected cycle graph on 4 nodes (1 is connected to 2 and 4, 2 is connected to 1 and 3, 3 is connected to 2 and 4, 4 is connected to 3 and 1).

When I find the cofactor along A11 I get 21, but when I find the cofactor along A12 I get 9. These are different! So this says that this graph has both 21 and 9 spanning trees?

Am I understanding this incorrectly?

Answer 1

I think you've made a mistake computing the Laplacian matrix.

I find \begin{bmatrix}2 & -1 &0 &-1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix}

You can check that any cofactor has determinant $4$, which you can check by inspection is the right number of trees.