RefacteA graph may have far too many spanning trees to list. Its incidence matrix has only one column per edge. The useful change of viewpoint is to make the columns carry the connectivity question, then ask a determinant to select the trees.
1. Replace a picture by differences
Take a finite connected loopless graph with n ≥ 2 vertices; parallel edges are allowed. Give each edge an arbitrary orientation. Its incidence column has −1 at the source, +1 at the target, and zero elsewhere. Collect the columns in a matrix B.
If p assigns a potential to every vertex, BTp records its change along every edge. Those changes sum to zero around a cycle: the intermediate potentials cancel. On a tree, the converse is immediate. Fix a root potential and integrate the edge changes along the unique paths.
The orientation keeps signs consistent; it does not change the underlying question. Adding a constant to every potential changes no edge difference. Remove that redundancy by setting the root potential to zero and deleting the corresponding row of B. Call the resulting matrix D.
2. Let a triangle show the mechanism
Orient the triangle as 0 → 1 → 2 → 0. Give those three edges positive weights a, b, c, respectively, and ground vertex 0. The matrices are
D = [ 1 −1 0 ] W = diag(a, b, c).
[ 0 1 −1 ]
With p = (p1, p2), the edge differences are p1, p2 − p1, −p2. Weighting those differences and collecting their vertex contributions produces the grounded Laplacian:
L = DWDᵀ = [ a+b −b ]
[ −b b+c ].
Its determinant is (a+b)(b+c) − b² = ab + ac + bc. Each term is the product of the weights of one spanning tree. Setting all three weights to one gives three trees. We should now explain why this is a mechanism, rather than a lucky expansion.
The matrix form is an ansatz suggested by the operations we want to retain. A column of D records one local edge difference; W weights it; the transpose collects the resulting contributions back at vertices. We choose this composition because its determinant expansion can test selections of edges. Its success still needs a proof.
3. Make the determinant select trees
For a set S of n−1 edges, write DS for their columns. The Cauchy–Binet determinant identity gives
Here is why that determinant identity performs the selection. For an r-by-m matrix B and an m-by-r matrix C, expand each column of BC as a sum of columns of B. Multilinearity produces an ordered choice of r columns. A choice repeating a column has determinant zero: in the permutation expansion, swap the two positions of that repeated column to pair opposite terms. Group the remaining choices by their unordered set S. Their signed orderings give exactly det(CS), leaving det(BS)det(CS). Take B=D and C=WDT; the diagonal weights factor out and the two minors agree.
A cycle makes its incidence columns dependent: follow the cycle and add the columns with their traversal signs. Their sum is zero. A set of n−1 edges that is not a spanning tree contains a cycle, because a forest on all n vertices has n minus its number of components edges. Consequently its determinant vanishes.
For a tree, choose a leaf other than the root. Its row has exactly one nonzero entry, equal to ±1. Expanding there removes that leaf and its edge. Repeat until the empty determinant, equal to one. Thus every tree minor is ±1.
After squaring, the determinant identity keeps each tree with coefficient one and rejects every other edge set. This proves the weighted matrix-tree formula. The graph problem has become a test of column independence, and the determinant performs the test for all candidate sets at once.
4. Read the same matrix another way
The quadratic form pTLp is the sum of the weighted squared edge differences. A nonzero grounded potential has a nonzero difference somewhere, so this energy is positive and L is invertible.
For unit weights in the triangle, inject one unit of current at vertex 1 and remove it at the grounded vertex. The two unknown potentials satisfy
Hence p1 = 2/3 and p2 = 1/3. The voltage drop per unit current is 2/3, the effective resistance between vertices 0 and 1. The three spanning trees also give that edge an inclusion probability of 2/3: exactly two contain it.
5. What became elementary?
One incidence description now supports three operations: transpose it to measure differences, form its weighted Gram matrix to collect energy, and take a determinant to count trees. The rigorous bridge is the behaviour of its minors. Different calculations use the same data without claiming that all graph questions have become linear algebra.
For another determinant identity whose terms can be paired explicitly, follow the walk-and-cycle proof of Cayley–Hamilton. Its ansatz retains both parts of a cancellation instead of collecting their monomials too early.
Continue with the full matrix-tree treatment, electrical resistance, or the projection that gives joint tree probabilities. The original study also explains the extra arithmetic needed for higher-dimensional trees.