Statement

Delete any row + corresponding column of L → (n-1)×(n-1) matrix. Its determinant = τ(G) = spanning tree count.

Advertisement

Complexity

O(V³) via Gaussian elimination on Laplacian.

Advertisement

Weighted version

Weighted Laplacian: L_ij = -w_ij for i≠j, L_ii = sum of edge weights. Determinant = sum of weights of all spanning trees.

Directed version

Directed spanning tree with fixed root. Diagonal cofactor of Laplacian counts arborescences rooted at that vertex.