Motivation
Knowing that a connected graph has a spanning tree does not tell us how many choices exist. Directly searching all edge subsets becomes expensive even when each candidate is easy to check. An incidence matrix converts the question into one determinant, with cancellation automatically removing cyclic choices.
Weights retain more information than a single count. A product of the edge weights records each tree, and their sum becomes a generating polynomial. Differentiating that polynomial then answers a probabilistic question about a randomly selected weighted tree.
The determinant identities are proved here; only finite-dimensional matrix multiplication and the multilinearity of determinants are assumed.
Definitions
Definition 1.6.1
(Labeled edges, incidence and the tree polynomial)
Let be a finite undirected multigraph on vertices, with labeled edges; loops and parallel edges are allowed. Give every edge a weight , initially an indeterminate over the rationals. A spanning tree contains every vertex, is connected and has no cycle; loops never belong to one, and two parallel edges form a cycle of length two.
Define
For one vertex, the empty tree contributes one, even if loops are present. A disconnected graph on more than one vertex has tree polynomial zero.
Orient each nonloop edge arbitrarily. Its incidence column has a minus one at its tail, a plus one at its head, and zero elsewhere. A loop has a zero column. Let be the resulting by matrix and the diagonal matrix of edge weights. The weighted Laplacian is . Its off-diagonal entry is minus the sum of weights of edges between those vertices; its diagonal is the sum of incident nonloop weights. This convention excludes loops from the diagonal as well.
Choose a root vertex and delete its row from , obtaining . Delete the root row and column from , obtaining . A zero by zero determinant is one.
Theorem/Proposition
Theorem 1.6.2
(Every principal Laplacian cofactor is the tree polynomial)
For every finite weighted multigraph and every chosen root,
The equality is a polynomial identity. In particular, unit weights count labeled spanning trees exactly, and the determinant does not depend on the arbitrary edge orientations or on which root was removed.
Theorem 1.6.3
(Complete and complete bipartite graphs have explicit counts)
For the simple complete graph on vertices, the number of spanning trees is . The one-vertex count is one. For a complete bipartite graph with positive part sizes , the count is
The formula includes stars and the single-edge graph; the positivity of both part sizes is part of the statement.
Theorem 1.6.4
(A positive weighted tree law has exact edge marginals)
Suppose is connected and all nonloop edge weights are positive real numbers. Select a spanning tree with probability proportional to its weight product. Let be edge 's reduced incidence column and let be the reduced Laplacian. Then
For a loop the right side is zero. The marginal probabilities sum to , and each lies between zero and one. Changing orientations leaves them unchanged.
Concept lensAlgebraic
One polynomial supports counting, sensitivity and random selection
Unit weights count trees, formal weights retain which edges occur, and positive numerical weights define a probability law. The determinant identity is common to all three uses, but invertibility and probabilistic division are invoked only under the later positivity and connectedness hypotheses.
The proofs below follow this order: the cofactor identity, then the two explicit families, then the probability law.
Proof sketch or proof idea
Determinant expansion singles out tree edge sets
The argument rests on a rectangular determinant expansion.
Lemma 1.6.5
(Cauchy–Binet expansion)
Let be a matrix and an matrix. Then
where runs over the -element subsets of ; the sum is empty when .
Proof
(Proof by column multilinearity)
If is a by matrix and an by matrix, multilinearity in the columns gives an expansion of over ordered choices of columns of . A choice with repeated indices has determinant zero. For a fixed unordered set of distinct indices, the sum over their orders is precisely , by the signed permutation formula for a determinant. Thus
If there are no distinct choices and the sum is zero. At there is exactly the empty choice and both sides are one. This proves the required Cauchy–Binet identity directly.
Proof
(Proof of the principal-cofactor formula)
Apply the Cauchy–Binet expansion to and . For each set of labeled edges, taking the selected diagonal factors out of the determinant gives
We now prove that the squared determinant is one exactly for spanning trees and zero otherwise.
If contains a loop, its incidence column is zero. If it contains a cycle, traverse that cycle and add its oriented incidence columns with signs chosen according to traversal direction. Every vertex contribution cancels, producing a nonzero linear dependence. This includes two parallel edges with their appropriate signs. Deleting one incidence row preserves the dependence, so the selected determinant vanishes.
If is acyclic, it is a forest. A forest on vertices with components has edges, by summing the tree edge count within its components, including isolated vertices. Here forces , so it is a spanning tree.
For a tree, prove the determinant has absolute value one by induction on . The case is the empty determinant. For , a tree has a leaf different from the chosen root: use the endpoints of a longest path, at least one of which is not that root. The leaf's reduced incidence row has exactly one nonzero entry, equal to plus or minus one. Expanding along that row reduces the determinant, up to sign, to the reduced incidence determinant of the tree with that leaf and edge removed. Induction completes the argument. Substituting these zero-or-one coefficients proves the formula.
Proof X-ray
The determinant is selecting bases of the incidence constraints
The three ingredients do separate jobs. The Cauchy–Binet expansion turns into a sum over all -edge sets, each weighted by ; because the minor is squared, orientation signs never matter. The cycle argument removes the non-trees: a cycle gives a signed dependence among incidence columns that survives deleting the root row, so sets containing a cycle or a loop contribute zero. The forest count makes every acyclic set of size connected, so only spanning trees survive.
The leaf expansion then closes the argument by fixing each surviving coefficient to one. Deleting the root row is essential there: the full incidence matrix of a tree is and not square, while for a leaf different from the root always exists. Without the root deletion, is singular, as the counterexample in the common mistakes shows.
Compute two important families without enumerating their trees
The explicit families need one more determinant fact.
Lemma 1.6.6
(Rank-one determinant update)
For an invertible square matrix and column vectors ,
Proof
(Proof by expanding a perturbed identity)
To prove it, factor out and expand by column multilinearity. Terms selecting the added vector in two columns vanish because those columns are proportional. The term selecting none is one; the single-column terms sum to . This proves the fact, including size zero under the natural empty-vector convention.
Proof
(Proof of the two explicit counts)
For the reduced Laplacian is of size , where has every entry one. The rank-one identity gives determinant . The argument also works at ; the single-vertex case was already defined separately.
For remove a root in the part of size . The diagonal blocks are and , with negative all-one off-diagonal blocks. Subtract suitable multiples of the first block's rows to eliminate the lower left block; these row additions preserve the determinant. The lower diagonal block becomes
Its determinant is . Multiplying by gives the stated answer. When , the second block is empty, and the same expression is one; no inverse of an empty-sized positive part is being required.
Positive weights turn the polynomial into a probability law
Proof
(Proof of the edge-marginal formula)
For a reduced vector , insert zero in its root coordinate to make a full vector . Then
With positive nonloop weights, this is zero only when is constant along every edge. Connectedness and the root's zero coordinate force . Hence is positive definite and invertible for ; the one-vertex empty matrix has the usual empty inverse convention.
The tree polynomial is linear in each separate weight. Therefore is the total weight of trees containing . On the matrix side, changing just by changes by . The rank-one determinant formula gives its derivative as . Divide the two equal derivatives by the positive normalizing polynomial to obtain the marginal formula.
Each tree has exactly edges, so summing the marginal indicators gives the asserted sum, without assuming edge independence. A loop has zero incidence and never enters a tree; reversing an edge negates both copies of its column and changes nothing.
Separate algorithmic computation from the identity
Constructing the Laplacian takes linear edge accumulation and quadratic matrix storage in a dense implementation. A determinant can be evaluated with cubic arithmetic work by elimination, choosing a nonzero row pivot when required. With positive weights the reduced matrix is positive definite, so exact elimination has nonzero diagonal pivots. These are arithmetic-operation statements; arbitrary rational input lengths and exact fraction growth require separate bit accounting, and floating-point reliability requires further analysis.
The formula also gives a direct polynomial identity useful without a numerical determinant algorithm. For a nonloop edge, divide trees into those omitting it and those containing it. Contracting that labeled edge bijects the latter with spanning trees of the contracted multigraph, preserving the other chosen edges. Thus . Contraction may create loops and parallel edges, which retain the conventions already stated. A loop is simply ignored.
Worked examples
Worked example 1.6.7
(A weighted triangle records all three possible deletions)
Give the three triangle edges weights . Its tree polynomial is . Removing the vertex shared by edges gives reduced matrix with diagonal entries and off-diagonal entries . Its determinant is .
At unit weights there are three trees and every edge has inclusion probability two thirds. At weights , the normalization is five and the edge with weight two occurs with probability four fifths. Its larger weight changes the law rather than creating four distinct labeled copies.
Worked example 1.6.8
(Parallel choices multiply, while loops contribute nothing)
Take vertices , two parallel edges of weights two and three between , and one edge of weight five between . Add a loop of any weight at . Every tree uses the bridge to and exactly one of the parallel edges, so its polynomial value is .
Rooting at gives the diagonal reduced matrix with entries five and five. The bridge marginal is one; the parallel marginals are two fifths and three fifths; the loop marginal is zero. Their sum is two, exactly the number of edges in every spanning tree.
Worked example 1.6.9
(Two graph families give counts of different scales)
The complete graph on five vertices has spanning trees. The complete bipartite graph with parts of sizes two and three has .
For the latter, rooting in the size-three part gives diagonal blocks and all-one negative off-diagonal blocks. The lower eliminated block is , with determinant ; the first block contributes nine, giving twelve. This small computation displays the block elimination rather than merely quoting the closed formula.
Common mistakes
Counterexample mode
The full Laplacian determinant is zero even for a connected graph
Every incidence column sums to zero, so the all-one vector lies in the full Laplacian's kernel. For the single-edge graph, the Laplacian has diagonal ones and off-diagonal minus ones; its determinant is zero although there is exactly one spanning tree. Deleting one root row and column gives the one by one matrix with entry one, the required cofactor.
Common mistake
(Putting loop weights on the diagonal)
A loop has a zero incidence column, so it contributes nothing to , and it never lies in a spanning tree. Adding its weight to a diagonal entry changes the cofactor: in the parallel-edge example rooted at , a loop of weight placed at and counted on the diagonal would raise the determinant from to , although the trees are unchanged.
Common mistake
(Merging labeled parallel edges)
Parallel edges are different labeled edges and give different spanning trees. Replacing the edges of weights and in the parallel-edge example by one edge of weight gives instead of . The generating count survives only if the merged edge carries the total weight , and even then the separate marginals and are lost.
Common mistake
(Reading marginals as independent inclusions)
The marginals sum to , but tree edges are generally dependent. In the unit-weight four-cycle each edge has probability , yet the four edges never occur together, whereas independent inclusion would give the positive probability . The inverse formula also needs a connected graph: if is disconnected and , then , is singular, and there is no law to normalize.
Summary
Incidence minors turn a Laplacian cofactor into the full weighted tree polynomial. Cycles vanish and tree minors have unit absolute determinant. Rank-one and block elimination give explicit complete and complete-bipartite counts, while positive weights yield exact edge marginals and a clear distinction between polynomial identities and inverse-based probability calculations.
Exercises
Quick check
(Find the spanning-tree count of a four-cycle and the inclusion probability of each edge under unit weights. Check the marginal sum.)
Every tree omits exactly one cycle edge.
Solution · Answer
Deleting any one of the four cycle edges leaves a spanning path, so there are four trees. Each specified edge is omitted by one of them and included by three, giving marginal . The four marginals sum to three, which equals for four vertices. The edges are not independent: their joint inclusion is impossible because the full cycle is not a tree.
Quick check
(Apply deletion–contraction to an edge of a unit-weight triangle. Explain why the contracted graph has two labeled parallel edges and how their count contributes.)
Retain multigraph edge identities after contraction.
Solution
Deleting the chosen triangle edge leaves a single spanning path, contributing one. Contracting it produces two vertices joined by two distinct labeled parallel edges. Either single edge is a spanning tree of that multigraph, contributing two. Deletion–contraction therefore gives .
Consolidating those parallel edges into one unweighted edge would incorrectly give two in total. Consolidating them into a single edge of weight two would preserve the generating count for this purpose, provided that the loss of separate marginal identities is understood.
Quick check
(Compute the tree count of and of the complete graph on four vertices. Explain why the first graph's edge marginals are all one.)
A star has only one possible spanning tree.
Solution · Answer
The bipartite formula gives . Every one of the star's seven edges is a bridge and belongs to the unique tree, so all seven marginals equal one and sum to seven. For the complete graph on four vertices the formula gives . Its extra cycles create choices; the two formulas are counting trees in different ambient graphs, not merely using the same vertex number.