Kirchhoff Matrix-Tree Count

Theory

For a simple undirected graph with n vertices, the Laplacian matrix L is defined as L = D - A, where D is the diagonal degree matrix and A is the adjacency matrix. The rows and columns of L sum to zero, so det(L) = 0. Kirchhoff's theorem states that for any vertex i, the cofactor obtained by deleting row i and column i is exactly equal to the number of spanning trees in the graph. If edges have weights w, the diagonal elements are the sum of weights of incident edges, and off-diagonal elements are -w if an edge exists and 0 otherwise. The cofactor then evaluates to the sum of products of weights over all spanning trees.

Experiment

Investigate the relationship between the graph structure, edge weights, and the resulting spanning tree count by interacting with the module controls. Go to the module.

1. Set the Graph to "Cycle" and Edge weight to 1. Note the Unweighted tree count and Laplacian cofactor are equal to 4.
2. Change the Edge weight to 2. Observe the Unweighted tree count remains 4, but the Weighted tree sum becomes 32.
3. Set the Graph to "Complete". Observe how the number of spanning trees increases substantially.
4. Try the "Disconnected" graph. Verify that the spanning tree count is 0, since no spanning tree can exist.
5. Observe that changing the "Deleted vertex" index shifts the deleted row and column of the Laplacian but yields the exact same determinant cofactor.

Worked Example

Let us calculate the tree count for a Cycle graph (C4) with unweighted edges (w=1) and vertex 0 deleted.

1. The graph C4 has n = 4 vertices and edges between (0,1), (1,2), (2,3), and (3,0).
2. The degrees of all vertices are 2. The unweighted Laplacian matrix L is a 4 × 4 matrix with 2 on the diagonal and -1 for adjacent vertices.
3. To find the cofactor, we delete row 0 and column 0 to obtain the 3 × 3 minor matrix M.

M = [ [ 2, -1,  0], [-1,  2, -1], [ 0, -1,  2] ]

Now we evaluate the determinant:

det(M) = 2 * (2 * 2 - (-1) * (-1)) - (-1) * ((-1) * 2 - (-1) * 0) + 0 det(M) = 2 * (4 - 1) + 1 * (-2 - 0) det(M) = 2 * (3) - 2 = 6 - 2 = 4

The expected result is exactly 4, which matches the known properties of a cycle graph C_n having exactly n spanning trees.

Limitations

The standard Matrix-Tree theorem enumeration does not explicitly identify or sample individual spanning trees, but merely evaluates the aggregate count or weight sum. The computation relies on calculating a matrix determinant, which for large graphs can be floating-point unstable and computationally expensive. Direct cofactor calculation scales as O(n³) for dense matrices.

References

Matrix-tree enumeration extensions and directed analogs are detailed extensively in this reference: https://arxiv.org/abs/1404.3876. This paper discusses advanced topics and generalizations of Kirchhoff's theorem to directed graphs and generating functions.