Computing Spanning-Tree Counts From Laplacian Cofactors

From a Graph to a Determinant

A spanning-tree count can be obtained without listing every spanning tree. The method converts the graph into a matrix, removes one row and the corresponding column, and evaluates the resulting determinant. For a small graph, row operations make this calculation manageable by hand. The determinant is not just an algebraic quantity: the Matrix-Tree Theorem identifies it with the number of spanning trees.

All graphs in this tutorial are finite and simple. A spanning tree of a graph \(G\) is a subgraph that contains every vertex of \(G\) and is a tree. In particular, a graph with one vertex has one spanning tree, consisting of that vertex and no edges. A disconnected graph has no spanning tree.

Definition: The Laplacian matrix \(\mathbf{L}(G)\) of a graph \(G\) is the matrix whose diagonal entry at vertex \(v\) is \(\deg(v)\), and whose entry at two distinct vertices \(u,v\) is \(-1\) if \(uv\in E(G)\) and \(0\) otherwise. A Laplacian cofactor is the determinant obtained by deleting one row and the column with the same index from \(\mathbf{L}(G)\).

To compute the cofactor, first form the full Laplacian using degrees in the original graph. Only then delete a row and column. The Matrix-Tree Theorem states that, for any finite graph \(G\), each Laplacian cofactor equals \(t(G)\), the number of spanning trees. This is the Matrix-Tree Theorem established in the earlier material; here we use it to turn determinant calculations into counts. In particular, if \(G\) is disconnected, \(t(G)=0\), so every such cofactor is zero.

Row Operations and Determinants

For hand calculations, the most convenient operation is replacing one row by itself plus a multiple of another row. This operation does not change the determinant. Once the matrix is upper triangular, its determinant is the product of its diagonal entries. Row swaps change the sign, and multiplying a row by a number multiplies the determinant by that number, so those operations require extra bookkeeping.

Lemma: If row replacements turn a square matrix \(A\) into an upper triangular matrix \(U\), without row swaps or row scaling, then \(\det(A)\) is the product of the diagonal entries of \(U\).

Proof. A row replacement \(R_i\leftarrow R_i+cR_j\), with \(i\ne j\), preserves the determinant: by linearity in row \(i\), the new determinant is the old determinant plus \(c\) times a determinant with rows \(i\) and \(j\) equal. The latter determinant is zero because the determinant is alternating. Thus all the stated row replacements preserve the determinant. For an upper triangular matrix, the permutation formula for the determinant has only one potentially nonzero term: the identity permutation, since any other permutation must select an entry below the diagonal. That term is the product of the diagonal entries. Therefore \(\det(A)=\det(U)\) equals that product. \(\square\)

This lemma explains the calculation procedure: eliminate entries below the diagonal using row replacements, then multiply the diagonal entries. Fractions may appear during elimination; they are valid, provided no row is silently scaled or swapped.

Worked Cofactor Calculations

Worked Example: A Four-Vertex Graph with a Chord

Let \(G\) have vertex set \(V=\{1,2,3,4\}\) and edge set \(E=\{12,23,34,41,13\}\). Find its spanning-tree count by a Laplacian cofactor.

The degrees are \(\deg(1)=3\), \(\deg(2)=2\), \(\deg(3)=3\), and \(\deg(4)=2\). In the vertex order \(1,2,3,4\), the Laplacian is

\mathbf{L}(G)= \begin{pmatrix} 3&-1&-1&-1\\ -1&2&-1&0\\ -1&-1&3&-1\\ -1&0&-1&2 \end{pmatrix}.

Delete row 4 and column 4. The cofactor matrix is

A= \begin{pmatrix} 3&-1&-1\\ -1&2&-1\\ -1&-1&3 \end{pmatrix}.

Use row replacements to make \(A\) upper triangular. First set \(R_2\leftarrow R_2+\frac13R_1\) and \(R_3\leftarrow R_3+\frac13R_1\). The rows become \((3,-1,-1)\), \((0,\frac53,-\frac43)\), and \((0,-\frac43,\frac83)\). Then set \(R_3\leftarrow R_3+\frac45R_2\). Its final entry is \(\frac83+\frac45(-\frac43)=\frac{40}{15}-\frac{16}{15}=\frac85\), so the resulting upper triangular matrix has diagonal entries \(3,\frac53,\frac85\). Therefore

\det(A)=3\cdot\frac53\cdot\frac85=8.

Check: There are five edges, so there are \(\binom{5}{3}=10\) three-edge subsets. The only three-edge subsets that are cycles are the triangles with edge sets \(\{12,23,13\}\) and \(\{13,34,41\}\). Every other three-edge subset is an acyclic graph on four vertices with three edges, hence a spanning tree. Thus the direct count is \(10-2=8\), agreeing with the cofactor.

Worked Example: A Triangle with a Two-Edge Tail

Let \(G\) have vertex set \(V=\{1,2,3,4,5\}\) and edge set \(E=\{12,23,31,34,45\}\). Compute \(t(G)\) by deleting vertex 5's row and column.

The degrees are \(2,2,3,2,1\), in vertex order \(1,2,3,4,5\). Deleting row 5 and column 5 from the Laplacian gives

A= \begin{pmatrix} 2&-1&-1&0\\ -1&2&-1&0\\ -1&-1&3&-1\\ 0&0&-1&2 \end{pmatrix}.

Apply \(R_2\leftarrow R_2+\frac12R_1\) and \(R_3\leftarrow R_3+\frac12R_1\). The rows become \((2,-1,-1,0)\), \((0,\frac32,-\frac32,0)\), \((0,-\frac32,\frac52,-1)\), and \((0,0,-1,2)\). Next, \(R_3\leftarrow R_3+R_2\) gives row 3 equal to \((0,0,1,-1)\). Finally, \(R_4\leftarrow R_4+R_3\) gives row 4 equal to \((0,0,0,1)\). The upper triangular diagonal is \(2,\frac32,1,1\), so

\det(A)=2\cdot\frac32\cdot1\cdot1=3.

Check: Edges 34 and 45 must both belong to any spanning tree, because each lies on the only route from the triangle to the vertices farther along the tail. Among the three triangle edges, a spanning tree must use exactly two: using all three makes a cycle, while using fewer fails to connect all three triangle vertices. There are exactly three choices for the omitted triangle edge, so the direct count is \(3\), as calculated.

Worked Example: Two Triangles Joined by a Bridge

Let \(G\) have vertex set \(V=\{1,2,3,4,5,6\}\) and edge set \(E=\{12,23,31,34,45,56,64\}\). The edge 34 joins the triangles on \(\{1,2,3\}\) and \(\{4,5,6\}\). Delete row 3 and column 3.

The degrees in the original graph are \(\deg(1)=2\), \(\deg(2)=2\), \(\deg(3)=3\), \(\deg(4)=3\), \(\deg(5)=2\), and \(\deg(6)=2\). With the remaining vertex order \(1,2,4,5,6\), the cofactor matrix is

A= \begin{pmatrix} 2&-1&0&0&0\\ -1&2&0&0&0\\ 0&0&3&-1&-1\\ 0&0&-1&2&-1\\ 0&0&-1&-1&2 \end{pmatrix}.

For the first two rows, \(R_2\leftarrow R_2+\frac12R_1\) changes the second row to \((0,\frac32,0,0,0)\). This block has diagonal product \(2\cdot\frac32=3\). For the last three rows, start with the block \(\begin{pmatrix}3&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix}\). Set \(R_2\leftarrow R_2+\frac13R_1\) and \(R_3\leftarrow R_3+\frac13R_1\). These rows become \((0,\frac53,-\frac43)\) and \((0,-\frac43,\frac53)\), after the unchanged first row \((3,-1,-1)\). Then \(R_3\leftarrow R_3+\frac45R_2\) makes its last entry \(\frac53-\frac{16}{15}=\frac{25}{15}-\frac{16}{15}=\frac35\). The block determinant is \(3\cdot\frac53\cdot\frac35=3\). The two blocks have no entries coupling them, so the determinant of \(A\) is the product \(3\cdot3=9\).

Check: A spanning tree must include bridge 34; without it, the two triangles remain disconnected. Within each triangle, exactly two of its three edges must be chosen. There are three choices in each triangle, independently, so the direct count is \(3\cdot3=9\).

Why the Order of Operations Matters

A Laplacian diagonal records the degree in the original graph. Deleting a row and column is an algebraic operation on that matrix; it does not mean first removing the corresponding vertex from the graph and then rebuilding the Laplacian. This distinction can change the determinant.

Common mistake. In the third example, vertex 3 is the deleted index, but vertex 4 still has degree 3 in the original graph: it is adjacent to 3, 5, and 6. If one incorrectly changes the diagonal entry 3 at vertex 4 to 2, the last block becomes \(\begin{pmatrix}2&-1&-1\\-1&2&-1\\-1&-1&2\end{pmatrix}\). Its rows sum to zero, so its determinant is zero, producing the incorrect spanning-tree count 0. The correction is to retain the original degree 3 when forming the cofactor. The correct block determinant is 3, giving the correct count 9.

Another bookkeeping pitfall is to scale a row without adjusting the determinant. For example, replacing a row by twice that row doubles the determinant; it is not one of the determinant-preserving row replacements used above. When using elimination, either avoid scaling and swapping, or explicitly record their effects.

A Reliable Calculation Checklist

List degrees and adjacencies.
Use the original graph to fill the Laplacian diagonal with degrees and each off-diagonal entry with \(-1\) or \(0\).

Choose an index to delete.
Remove its row and the column with the same index. The Matrix-Tree Theorem says this cofactor gives \(t(G)\).

Eliminate below the diagonal.
Use row replacements, writing down each changed row and any fractions. Avoid untracked row swaps or scaling.

Multiply and verify.
Multiply the triangular diagonal entries, then check the count independently when the graph's structure makes direct enumeration possible.

The cofactor method is especially useful when a graph is too large for a convenient list of spanning trees but its Laplacian remains small enough to handle. For hand calculations, an independent structural count is a valuable check: forced edges, separate cycles, or a short list of edge subsets can reveal an arithmetic or setup error. The determinant method and direct counting serve different purposes—the first is systematic, while the second can confirm that the answer has the right value.

Check Your Understanding

For each question, state the graph or matrix data needed and show enough work to justify the conclusion.

For the graph on \(\{1,2,3\}\) with edges \(\{12,23,31\}\), write its Laplacian, form a cofactor, and compute the spanning-tree count.
Why must the degrees be calculated before deleting a row and column? Illustrate your explanation using vertex 4 in the two-triangle example.
Suppose row replacements produce an upper triangular matrix with diagonal entries \(2, \frac32, 1\). What is its determinant, provided no row swaps or scalings were used?
Explain why a disconnected graph has zero spanning trees and what the Matrix-Tree Theorem then implies about its Laplacian cofactors.
In the four-vertex chord example, explain why every three-edge subset other than the two triangles is a spanning tree.