Spanning-Tree Counts In Cycles And Complete Bipartite Examples

Two Ways to Count Spanning Trees

A spanning tree connects all vertices of a graph without containing a cycle. In some graphs, the structure forces a simple description of every spanning tree. In others, a Laplacian cofactor provides an efficient calculation. These methods complement one another: a direct count explains why the answer has its particular form, while a cofactor gives an independent numerical check.

All graphs considered here are finite and simple. A spanning tree of a connected graph \(G=(V,E)\) is a subgraph with vertex set \(V\) that is connected and has no cycles. We write \(t(G)\) for the number of spanning trees of \(G\). A tree on \(n\) vertices has \(n-1\) edges, so each spanning tree of a graph of order \(n\) has exactly \(n-1\) edges.

We will use the Matrix-Tree Theorem, established in the earlier material on Laplacian cofactors: for a connected graph, deleting the same row and column of \(\mathbf{L}\) gives a matrix whose determinant is \(t(G)\). The result does not depend on which vertex is chosen for deletion. Our calculations below apply this theorem; the direct arguments will also give counts without determinants.

Cycles: One Omitted Edge

Proof. Label the edges of \(C_n\) in cyclic order as \(e_1,\ldots,e_n\). A spanning tree cannot contain all \(n\) edges, since that would leave the cycle intact. It must have \(n-1\) edges, so it omits exactly one edge. Conversely, omitting any one of the \(n\) edges leaves a path through all \(n\) vertices, which is connected and has no cycle. The choices of omitted edge give distinct spanning trees, hence \(t(C_n)=n\). \(\square\)

The same count follows from a Laplacian cofactor. Delete one vertex of \(C_n\). The remaining \(n-1\) vertices form a path in the order inherited from the cycle, but each still has degree \(2\) in the original graph. Thus the cofactor matrix has \(2\) on its diagonal, \(-1\) immediately above and below the diagonal, and \(0\) elsewhere.

Let \(D_k\) be the determinant of the \(k\) by \(k\) matrix of this form. Set \(D_0=1\), the determinant of the empty matrix, and \(D_1=2\). Expanding along the last row gives \(D_k=2D_{k-1}-D_{k-2}\) for \(k\ge2\): the diagonal entry contributes \(2D_{k-1}\), and the adjacent \(-1\) entry contributes \(-D_{k-2}\). Induction gives \(D_k=k+1\). Indeed, this holds for \(k=0,1\); if it holds for \(k-1\) and \(k-2\), then \(D_k=2k-(k-1)=k+1\). The cofactor has size \(n-1\), so its determinant is \(D_{n-1}=n\), agreeing with the direct count.

A Direct Count for \(K_{2,n}\)

Write the two parts of \(K_{2,n}\) as \(A=\{a_1,a_2\}\) and \(B=\{b_1,\ldots,b_n\}\), where \(n\ge1\). Every edge joins a vertex of \(A\) to a vertex of \(B\). This structure lets us describe every spanning tree exactly.

Proof. Consider a spanning tree \(T\) of \(K_{2,n}\). Each of the \(n\) vertices in \(B\) has degree at least \(1\) in \(T\), since \(T\) is connected and has more than one vertex. The tree has \(n+2\) vertices and hence \(n+1\) edges. Because every edge has exactly one endpoint in \(B\), the sum of the degrees in \(B\) is \(n+1\). Subtracting the minimum possible total degree \(n\), the total excess is \(1\). Therefore exactly one vertex of \(B\) has degree \(2\), and every other vertex of \(B\) has degree \(1\). The degree-\(2\) vertex must be adjacent to both \(a_1\) and \(a_2\), since those are its only possible neighbors. There are \(n\) choices for this vertex. Each of the remaining \(n-1\) vertices of \(B\) chooses one of its two neighbors, giving \(2^{n-1}\) choices. Every such choice is connected, because the degree-\(2\) vertex links \(a_1\) to \(a_2\), and every other vertex is attached to one of them. It has \(n+1\) edges on \(n+2\) vertices and contains no cycle: a vertex of degree \(1\) cannot lie on a cycle, and the remaining three vertices form a path. Thus each choice gives a spanning tree, and all spanning trees arise this way. The count is \(n\,2^{n-1}\). \(\square\)

Checking \(K_{2,3}\) with a Laplacian Cofactor

The direct count is short, but the cofactor provides a useful independent verification. In a Laplacian, each diagonal entry is the vertex degree, each off-diagonal entry is \(-1\) when the two vertices are adjacent, and it is \(0\) otherwise. For \(K_{2,3}\), the two vertices in \(A\) have degree \(3\), while the three vertices in \(B\) have degree \(2\).

A Star as a Boundary Example

The complete bipartite graph \(K_{1,n}\) has one center and \(n\) leaves. It has no choice of edges to make: omitting any edge disconnects its leaf, while retaining all edges gives a connected graph with no cycle. This gives one spanning tree. Its cofactor calculation is especially simple and helps check that the methods also handle a part of size \(1\).

Common Pitfalls and How the Counts Help

Do not forget to choose the connecting vertex in \(B\). A tempting but incorrect count for \(K_{2,3}\) is \(2^3=8\), obtained by choosing one endpoint for each of the three vertices in \(B\). That count cannot connect \(a_1\) to \(a_2\): if every vertex of \(B\) chooses only one endpoint, there is no path between the two vertices of \(A\). The correction is to choose one vertex of \(B\) to connect both endpoints, then assign each other vertex to either endpoint. This gives \(3\cdot2^2=12\), not \(8\).

The two methods are useful in different circumstances. A direct argument is strongest when every spanning tree can be classified by a small number of structural choices, as for cycles and \(K_{2,n}\). A Laplacian cofactor is a reliable check and applies even when such a classification is not apparent. In either method, keep the target fixed: spanning trees use all vertices, are connected, and have no cycles. A count of edge subsets without establishing these properties is not yet a spanning-tree count.