The Weighted Matrix-Tree Theorem

From a Spanning-Tree Count to a Weighted Sum

In an unweighted graph, every spanning tree contributes one to the spanning-tree count. Assigning a nonnegative weight to each edge changes the question: a tree containing high-weight edges should contribute differently from one containing low-weight edges. The weighted matrix-tree theorem gives a single determinant that sums these contributions exactly. Its proof uses the incidence-matrix description of the Laplacian and a determinant expansion over sets of edges.

Throughout, \(G=(V,E)\) is a finite simple graph with \(n=|V|\ge 1\), and each edge \(e\in E\) has a specified weight \(w_e\ge 0\). A spanning tree is a connected, acyclic subgraph with vertex set \(V\). The weight of a spanning tree \(T\) is the product of the weights of its edges; for the tree on one vertex, the product over its empty edge set is defined to be \(1\).

If every edge has weight \(1\), then \(\mathbf{L}_w\) is the ordinary graph Laplacian. With general weights, the diagonal records weighted degree, while the off-diagonal entries record the negative edge weights. The theorem below says that deleting any one row and its matching column produces a determinant that sums tree weights, not just the number of trees.

The Weighted Matrix-Tree Theorem

In particular, the theorem covers weights equal to zero: any tree using a zero-weight edge contributes zero. The theorem also covers disconnected graphs, where there is no spanning tree. We prove it from two determinant facts, giving the needed arguments so that the role of each part is explicit.

Two Determinant Facts for the Proof

Choose an arbitrary orientation of each edge; this only chooses which endpoint is called the tail and which the head. The incidence matrix \(\mathbf{B}\) has one row per vertex and one column per edge. In the column for an oriented edge from \(u\) to \(v\), put \(-1\) in row \(u\), \(1\) in row \(v\), and \(0\) in every other row. Let \(\mathbf{W}\) be the diagonal matrix with diagonal entries \(w_e\), in the same edge order as the columns of \(\mathbf{B}\). Each edge contributes \(w_e\) to the two endpoint diagonal entries of \(\mathbf{BWB}^{\mathsf T}\) and \(-w_e\) to the two corresponding off-diagonal entries. Thus \(\mathbf{L}_w=\mathbf{BWB}^{\mathsf T}\).

Delete row \(r\) from \(\mathbf{B}\), obtaining \(\mathbf{B}_r\). The factorization gives \(\mathbf{L}_w^{(r)}=\mathbf{B}_r\mathbf{W}\mathbf{B}_r^{\mathsf T}\).

Proof. For \(p>0\), write the \(j\)-th column of \(\mathbf{X}\mathbf{Y}\) as \(\sum_{k=1}^m Y_{kj}\mathbf{x}_k\), where \(\mathbf{x}_k\) is column \(k\) of \(\mathbf{X}\). Multilinearity of the determinant in its columns expands \(\det(\mathbf{X}\mathbf{Y})\) as a sum over choices \(k_1,\ldots,k_p\), with term \(\bigl(\prod_{j=1}^pY_{k_jj}\bigr)\det(\mathbf{x}_{k_1},\ldots,\mathbf{x}_{k_p})\). A repeated index gives a determinant with repeated columns, hence contributes zero. For any fixed set \(S=\{s_1<\cdots<s_p\}\), the remaining terms using exactly those indices correspond to their \(p!\) orderings. Reordering the columns contributes the sign of that ordering times \(\det(\mathbf{X}_{[:,S]})\); the signed sum of the corresponding products of entries of \(\mathbf{Y}\) is \(\det(\mathbf{Y}_{[S,:]})\), by the determinant formula. Grouping the terms by \(S\) proves the identity. For \(p=0\), both sides equal \(1\) under the empty-determinant convention. \(\square\)

The next fact identifies the minors that occur when this expansion is applied to an incidence matrix.

Proof. If \(S\) contains a cycle, orient the traversal around that cycle. The signed sum of the incidence columns for its edges is zero, since each vertex on the cycle receives one \(1\) and one \(-1\). Changing the signs of columns to match the traversal does not affect linear dependence. Deleting row \(r\) preserves the resulting dependence, so the determinant is zero.

Now suppose the graph with edge set \(S\) has no cycle. A finite forest on \(n\) vertices with \(c\) connected components has \(n-c\) edges: each component with \(q\) vertices has \(q-1\) edges, as follows by repeatedly removing a leaf from a nontrivial tree; summing over the components gives the formula, including isolated vertices. Since \(|S|=n-1\), we get \(n-c=n-1\), so \(c=1\). Thus \(S\) is a spanning tree.

It remains to show that the incidence minor of a spanning tree has determinant \(1\) or \(-1\). We use induction on \(n\). For \(n=1\), the minor is empty and has determinant \(1\). For \(n>1\), a finite tree has at least two leaves: the endpoints of a longest path each have degree one, since another neighbor would either extend the path or make a cycle. At least one leaf \(\ell\) is different from \(r\). In \(\mathbf{B}_{r,S}\), row \(\ell\) has exactly one nonzero entry, equal to \(1\) or \(-1\), in the column of its incident edge. Expanding along that row leaves, up to sign, the incidence minor of the tree formed by deleting \(\ell\) and its incident edge, with row \(r\) still deleted. The smaller graph is a tree on \(n-1\) vertices, so induction gives determinant \(1\) or \(-1\). This proves the claim in both cases. \(\square\)

Proof of the Theorem

Proof. First suppose \(n>1\), and set \(p=n-1\). Use the determinant expansion lemma with \(\mathbf{X}=\mathbf{B}_r\) and \(\mathbf{Y}=\mathbf{W}\mathbf{B}_r^{\mathsf T}\). For each set \(S\) of \(p\) edges, the corresponding term is \(\det(\mathbf{B}_{r,S})\det(\mathbf{W}_{[S,S]}\mathbf{B}_{r,S}^{\mathsf T})\). The second determinant equals \(\bigl(\prod_{e\in S}w_e\bigr)\det(\mathbf{B}_{r,S}^{\mathsf T})\), because \(\mathbf{W}_{[S,S]}\) is diagonal. Also, a matrix and its transpose have the same determinant. Therefore the term is \(\det(\mathbf{B}_{r,S})^2\prod_{e\in S}w_e\).

By the incidence-minor lemma, this term is zero unless \(S\) is the edge set of a spanning tree, and it equals \(\prod_{e\in S}w_e\) when \(S\) is such an edge set. Summing over all \(S\) proves the formula. If the graph is disconnected, there is no such \(S\), so the same expansion gives zero. If \(n=1\), there is one spanning tree, with empty edge set and weight \(1\), while the deleted Laplacian minor is \(0\times0\) and has determinant \(1\). Thus the statement holds in every case. \(\square\)

The proof also explains why the choice of deleted vertex does not affect the answer: for every root \(r\), the corresponding cofactor equals the same sum over spanning trees.

Why the Weighting Matters

The sum in the theorem is a polynomial in the edge weights: each spanning tree contributes one product, with one factor for each of its edges. Setting every weight to \(1\) makes every tree contribute \(1\), recovering the ordinary matrix-tree theorem. If all weights are multiplied by a constant \(c\), then each spanning tree weight is multiplied by \(c^{n-1}\), because every spanning tree has \(n-1\) edges. The cofactor has the same scaling, as also follows from the theorem.

Nonnegative weights allow the theorem to include edges that are unavailable for a particular count by assigning them weight zero. More generally, the identity is an algebraic polynomial identity, but nonnegative weights make its interpretation as a sum of contributions especially direct. For a connected graph with positive edge weights, every spanning tree contributes a positive amount; for a disconnected graph, there is no spanning tree and every Laplacian cofactor is zero.

Common Pitfall

Do not substitute the unweighted tree count for the weighted sum. In the triangle example, there are three spanning trees, but the weighted answer is not \(3\). The incorrect calculation “there are three trees, so the cofactor is \(3\)” treats each tree as weight \(1\). The correct calculation multiplies the edge weights within each tree: \(2\cdot3=6\), \(2\cdot5=10\), and \(3\cdot5=15\), giving \(6+10+15=31\). The weighted Laplacian cofactor is \(31\), not \(3\).