Loops, Parallel Edges, And Spanning-Tree Counts

Spanning Trees When Edges Repeat

For a simple graph, an edge is determined by its pair of endpoints. In a multigraph, several distinct edge instances may join the same two vertices, and an edge may have both endpoints at the same vertex: such an edge is a loop. These possibilities do not change the basic idea of a spanning tree, but they do affect how trees are counted. In particular, parallel edges represent distinct choices, while loops represent no valid choice in a tree.

Write \(t(G)\) for the number of spanning trees. Throughout, \(G\) has at least one vertex. If \(G\) is disconnected, \(t(G)=0\); for a graph with one vertex, the empty edge set is a spanning tree, so \(t(G)=1\), even if the graph also has loops. When edge instances are listed, labels such as \(e_1,e_2\) distinguish parallel edges.

What Loops and Parallel Edges Do

Proof. A spanning tree is acyclic, so it cannot contain a loop, since a loop is itself a cycle. Therefore every spanning tree of \(G\) is a spanning tree of \(G-e\) when \(e\) is a loop. Conversely, deleting a loop removes no spanning tree, because none used \(e\). This gives a bijection and hence \(t(G)=t(G-e)\).

For parallel edges, regard each edge instance as a separate element of the edge set. A spanning tree that contains one particular instance remains a different edge set if that instance is replaced by another parallel instance, provided the replacement is the only chosen edge between those endpoints. More generally, the count is over edge-instance subsets, not just over endpoint pairs. A tree cannot contain two parallel instances together because they form a cycle of length two. \(\square\)

This distinction is important in deletion–contraction. For a nonloop edge instance \(e\), the recurrence is \(t(G)=t(G-e)+t(G/e)\), where \(G/e\) contracts the endpoints of \(e\). All other edge instances are retained: parallel edges to \(e\) become loops after contraction, and other parallel edges remain distinct. Trees not containing \(e\) are counted by \(G-e\); trees containing \(e\) correspond, after contracting \(e\), to trees of \(G/e\). The loops created by contraction cannot belong to those trees, just as the corresponding redundant edges could not be included alongside \(e\) in a tree of \(G\).

The Laplacian Convention for a Multigraph

To compare direct counting with a cofactor calculation, the Laplacian must encode edge multiplicities. Orient each nonloop edge instance arbitrarily and give it an incidence column with a \(+1\) at one endpoint and a \(-1\) at the other. Give each loop the zero column. If \(B\) is the resulting incidence matrix, define \(\mathbf L(G)=BB^{\mathsf T}\). Reversing an edge orientation changes the sign of one column but does not change \(BB^{\mathsf T}\).

This convention agrees with \(\mathbf L=\mathbf D-\mathbf A\) if loops contribute \(2\) to the degree and the adjacency-matrix diagonal entry for each loop is also \(2\). The two contributions cancel in \(\mathbf D-\mathbf A\). Using incidence columns makes the loop cancellation explicit and avoids ambiguity about adjacency-matrix conventions. Parallel edges each contribute separately, so their multiplicity appears in the entries of \(\mathbf L\).

Proof. Fix a vertex \(r\). Delete the row of \(r\) from the incidence matrix \(B\), obtaining \(B_r\). Deleting row \(r\) and column \(r\) from \(BB^{\mathsf T}\) gives \(B_rB_r^{\mathsf T}\). By the Cauchy–Binet formula, for an \(n\)-vertex graph with \(m\) edge instances,

Here \(B_r[:,S]\) is the square matrix formed from the columns for the edge instances in \(S\). If \(S\) contains a loop, its column is zero, so its determinant is zero. If \(S\) contains a cycle, the signed sum of the incidence columns around that cycle is zero; this also applies to a cycle made of two parallel edges. Therefore its columns are dependent and its determinant is zero.

Now suppose the \(n-1\) edge instances in \(S\) contain no cycle. They form a forest. A forest on \(n\) vertices with \(c\) components has \(n-c\) edges: each component with \(q\) vertices is a tree and has \(q-1\) edges, and summing over components gives \(n-c\). Since \(S\) has \(n-1\) edges, \(n-c=n-1\), so \(c=1\). Thus \(S\) is a spanning tree.

For a spanning tree \(S\), \(\det(B_r[:,S])\) is \(1\) or \(-1\). To verify this, if \(n=1\), the matrix is empty and its determinant is \(1\). If \(n>1\), the tree has a leaf different from \(r\): a tree with at least two vertices has at least two leaves, so at least one is not \(r\). The row of this leaf has just one nonzero entry, equal to \(1\) or \(-1\). Expanding the determinant along that row reduces its absolute value to the determinant for the smaller tree obtained by removing the leaf and its incident edge. Repeating this step ends at the one-vertex case, giving absolute value \(1\).

Consequently, each spanning tree contributes \(1\) to the Cauchy–Binet sum, and every other set \(S\) contributes \(0\). The sum is exactly the number of spanning trees. If \(G\) is disconnected, no such \(S\) can be a spanning tree, so the determinant and \(t(G)\) are both zero. This proves the formula for every \(n\ge1\), including \(n=1\). \(\square\)

Matching the Two Counting Methods

Common Pitfall: Simplifying Before Counting

A frequent error is to replace every bundle of parallel edges by a single edge before counting. In the two-vertex example, that would leave one connection and lead to the incorrect count \(1\), rather than the actual count \(3\). The simplified graph records whether a connection exists, but loses which edge instance was selected. It can represent the underlying connectivity, but it cannot preserve the edge-instance spanning-tree count unless the multiplicities are retained separately.

A related error is to add a loop to a diagonal entry of \(\mathbf L\) while leaving the other matrix entries unchanged. Under the incidence convention, a loop has a zero column and contributes nothing to \(\mathbf L\). If using \(\mathbf D-\mathbf A\), use a consistent convention: count each loop twice in both the degree and the adjacency diagonal so the contributions cancel. The cofactor formula then agrees with direct enumeration, which never includes loops in a spanning tree.