Kirchhoff Matrix-Tree Count

The Matrix-Tree theorem, discovered by Gustav Kirchhoff, expresses the number of spanning trees in a graph as the determinant of a modified Laplacian matrix.

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.