Worked Spanning-Tree Counts For Explicit Graphs

Counting Spanning Trees in a Specific Graph

A graph can have many spanning trees even when its vertex and edge sets are small. The right counting method depends on its structure: a cycle invites direct edge choices, a suitable edge gives a deletion–contraction recurrence, prescribed degrees lead to Prüfer codes, and a Laplacian cofactor gives a determinant. This tutorial works through these methods on explicit graphs and checks each answer independently.

All graphs are finite. Unless stated otherwise, they are simple and undirected. A spanning tree of \(G=(V,E)\) is a subgraph with vertex set \(V\) that is connected and has no cycles. Write \(t(G)\) for the number of spanning trees of \(G\). If \(G\) is disconnected, then \(t(G)=0\); for a graph with one vertex and no edges, the graph itself is its unique spanning tree, so \(t(G)=1\).

In a multigraph, distinct parallel edges are treated as distinct choices in a spanning tree. A loop cannot belong to a spanning tree, since it is a cycle by itself. These conventions matter when contraction is used: contracting an edge can create parallel edges or loops.

Edge Exchange and a Direct Count

Lemma (edge exchange): Let \(T\) be a spanning tree of a connected graph \(G\), and let \(e=uv\) be an edge of \(G\) not in \(T\). Adding \(e\) to \(T\) creates exactly one cycle. Removing any edge of that cycle produces another spanning tree of \(G\).

Proof. Since \(T\) is a tree, there is a unique path in \(T\) from \(u\) to \(v\). Adding \(e\) to that path forms a cycle. Any cycle in \(T+e\) must use \(e\), because \(T\) has no cycles; after removing \(e\), such a cycle would give a second \(u\)-\(v\) path in \(T\). Thus the cycle is unique. If an edge on this cycle is removed, the resulting graph has no cycle: any remaining cycle would also have been a cycle in \(T+e\), but the only one has been broken. It remains connected because removing an edge from a cycle leaves an alternate route between that edge’s endpoints. Hence the result is a spanning tree. \(\square\)

Edge exchange explains how one spanning tree can be changed into another, and can help organize a count. It does not, by itself, give the number of trees: the choices still have to be classified or counted.

Worked Example: A Four-Cycle with a Diagonal

Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{13,32,24,41,12\}\). The first four edges form the cycle \(1,3,2,4,1\), and \(12\) is a diagonal. Count the spanning trees.

A spanning tree on four vertices has three edges. First consider trees that do not contain \(12\). They must use three of the four cycle edges. Each choice is obtained by omitting one cycle edge, and the remaining path is connected and acyclic. This gives \(4\) trees.

Now consider trees containing \(12\). They need two more edges, chosen from \(13,32,24,41\). The pairs \(13,32\) and \(24,41\) fail: with \(12\), the first pair leaves vertex \(4\) isolated, and the second leaves vertex \(3\) isolated. The other four pairs work:

\(\{13,24\}\): the two cycle edges form components \(\{1,3\}\) and \(\{2,4\}\), joined by \(12\).
\(\{32,41\}\): the two cycle edges form components \(\{2,3\}\) and \(\{4,1\}\), joined by \(12\).
\(\{13,41\}\): together with \(12\), these edges connect all four vertices without a cycle.
\(\{32,24\}\): together with \(12\), these edges connect all four vertices without a cycle.

Thus the total is \(4+4=8\). Edge exchange can be seen, for example, starting with \(T=\{13,32,24\}\). Adding \(12\) creates the cycle \(1,3,2,1\); removing \(13\) gives \(\{12,32,24\}\), and removing \(32\) gives \(\{12,13,24\}\). Both are spanning trees containing the diagonal.

Check: For \(T=\{13,32,24\}\), the path between the endpoints of \(12\) is \(1,3,2\). Adding \(12\) therefore creates exactly the stated cycle. The two exchanged edge sets each have three edges, connect all four vertices, and contain no cycle.

Deletion–Contraction

Theorem (deletion–contraction): If \(G\) is a connected graph and \(e\) is a non-loop edge, then \(t(G)=t(G-e)+t(G/e)\). Here \(G-e\) deletes \(e\), and \(G/e\) contracts its endpoints; loops created by contraction are discarded, while parallel edges are retained as distinct edges.

Proof. Divide the spanning trees of \(G\) into two disjoint classes. A tree in the first class omits \(e\), so it is exactly a spanning tree of \(G-e\), and this class has size \(t(G-e)\). In the second class, every tree contains \(e\). Contract \(e\) in such a tree and remove the contracted edge. The result is connected and acyclic on the contracted vertex set, so it is a spanning tree of \(G/e\). Conversely, a spanning tree of \(G/e\) lifts to a spanning tree of \(G\) containing \(e\): replace each selected edge by its original edge, then restore \(e\). Parallel edges remain distinguishable, so this correspondence preserves the choices. The two constructions are inverse, and the second class has size \(t(G/e)\). Adding the class sizes proves the formula. \(\square\)

The graph \(G-e\) need not be connected; in that case it contributes zero. The recurrence also applies when contracting \(e\) creates parallel edges, because the distinct original edges give distinct spanning trees after contraction.

Worked Example: A Triangle with a Pendant Edge

Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,31,34\}\). Apply deletion–contraction to \(e=12\).

Deleting \(12\) leaves edges \(23,31,34\). These form the path \(2,3,1\) with the additional edge \(34\), which is the path \(2,3,4\) together with \(31\); in fact the edges connect all vertices without a cycle. Thus \(t(G-12)=1\).

Contracting \(12\) merges vertices \(1\) and \(2\) into a vertex \(x\). Edges \(23\) and \(31\) become two distinct parallel edges from \(x\) to \(3\), and \(34\) remains. A spanning tree must use \(34\) and exactly one of the two parallel \(x3\) edges. Therefore \(t(G/12)=2\), and deletion–contraction gives \(t(G)=1+2=3\).

Check: In the original graph, edge \(34\) is forced because it is the only edge incident to \(4\). The other two selected edges must connect the triangle’s three vertices without a cycle. Any two of \(12,23,31\) do so, giving \(\binom{3}{2}=3\) spanning trees, as the recurrence gives.

Prüfer Codes for Prescribed Degrees

Prüfer codes count labeled trees when the degrees are specified. A labeled tree on \(n\ge2\) vertices has a Prüfer sequence of length \(n-2\). In the sequence, label \(i\) occurs exactly \(d_i-1\) times if vertex \(i\) has degree \(d_i\). The reason is that each time \(i\) is recorded during encoding, one incident edge is removed while \(i\) remains; its final remaining incident edge accounts for the additional \(1\) in its degree. The Prüfer correspondence is a bijection, so counting the allowed sequences counts the trees.

Counting rule: For positive prescribed degrees \(d_1,\dots,d_n\) with \(\sum_i d_i=2(n-1)\), the number of labeled trees with those degrees is \(\dfrac{(n-2)!}{\prod_{i=1}^n(d_i-1)!}\). This counts permutations of the Prüfer multiset, in which label \(i\) occurs \(d_i-1\) times.

Worked Example: Five Labeled Vertices with Prescribed Degrees

Count the trees on \(V=\{1,2,3,4,5\}\) with degrees \(d(1)=3\), \(d(2)=2\), and \(d(3)=d(4)=d(5)=1\). The degree sum is \(3+2+1+1+1=8=2(5-1)\), as required. The Prüfer sequence has length \(3\) and contains two \(1\)'s and one \(2\). Its possible sequences are \(112,121,211\), so there are three trees.

Decode them to check the count. At each step, join the smallest label absent from the remaining sequence to its first entry; remove that label and the first entry. Then join the last two remaining labels.

For \(112\), the first absent label is \(3\), giving \(31\). The remaining sequence is \(12\) on labels \(\{1,2,4,5\}\); the smallest absent label is \(4\), giving \(41\). The remaining sequence is \(2\) on \(\{1,2,5\}\); the smallest absent label is \(1\), giving \(12\). The final edge is \(25\). The tree edges are \(31,41,12,25\).
For \(121\), the first absent label is \(3\), giving \(31\). With sequence \(21\) on \(\{1,2,4,5\}\), the smallest absent label is \(4\), giving \(42\). With sequence \(1\) on \(\{1,2,5\}\), the smallest absent label is \(2\), giving \(21\). The final edge is \(15\). The tree edges are \(31,42,21,15\).
For \(211\), the first absent label is \(3\), giving \(32\). With sequence \(11\) on \(\{1,2,4,5\}\), the smallest absent label is \(4\), giving \(41\). With sequence \(1\) on \(\{1,2,5\}\), the smallest absent label is \(2\), giving \(21\). The final edge is \(15\). The tree edges are \(32,41,21,15\).

Check: In the three decoded trees, vertex \(1\) has degree \(3\), vertex \(2\) has degree \(2\), and vertices \(3,4,5\) each have degree \(1\). The formula also gives \(3!/(2!1!0!0!0!)=3\), agreeing with the explicit list.

Laplacian Cofactors

When the graph’s structure does not make a direct count convenient, the Matrix-Tree Theorem turns the problem into a determinant. The Laplacian matrix is \(\mathbf{L}=\mathbf{D}-\mathbf{A}\), where \(\mathbf{D}\) has the vertex degrees on its diagonal and \(\mathbf{A}\) is the adjacency matrix. For a connected graph, deleting the same row and column from \(\mathbf{L}\) gives a cofactor whose determinant is \(t(G)\). This is the Matrix-Tree Theorem, established in the earlier material on Laplacian cofactors and spanning-tree counts.

Worked Example: A Laplacian Cofactor for a Diamond

Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,24\}\); this is \(K_4\) with edge \(34\) removed. The degrees are \(3,3,2,2\). Delete row and column \(4\) from the Laplacian. The resulting cofactor matrix, in vertex order \(1,2,3\), is

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

Expanding along the first row gives

\begin{aligned} \det \begin{pmatrix} 3&-1&-1\\ -1&3&-1\\ -1&-1&2 \end{pmatrix} &=3(3\cdot2-(-1)(-1)) -(-1)((-1)\cdot2-(-1)(-1))\\ &\qquad+(-1)((-1)(-1)-3(-1))\\ &=3(6-1)-(-1)(-3)+(-1)(4)\\ &=15-3-4\\ &=8. \end{aligned}

So the Matrix-Tree Theorem gives \(t(G)=8\). Check independently by classifying trees according to how many of the edges \(14,24\) they use. If exactly one is used, choose it in \(2\) ways and choose \(2\) of the triangle edges \(12,13,23\) in \(3\) ways. Every such choice connects all vertices without a cycle, giving \(2\cdot3=6\). If both \(14\) and \(24\) are used, exactly one triangle edge is needed to include vertex \(3\). The choices \(13\) and \(23\) work; \(12\) would make a cycle on \(\{1,2,4\}\) and leave \(3\) isolated. This gives \(2\) more trees, for \(6+2=8\).

Check: The determinant and the direct count both give \(8\). The second count covers every tree: it must use at least one of \(14,24\) to include vertex \(4\), and the two cases—exactly one or both—are disjoint.

Choosing and Checking a Count

Each method has a natural setting. Use edge exchange to understand how trees change when an edge is added or replaced; combine it with a structural classification rather than treating exchange as a count on its own. Use deletion–contraction when splitting trees according to whether one particular edge is present leads to smaller, manageable graphs. Use Prüfer codes for labeled trees with specified degrees, where the allowed sequences can be counted directly. Use a Laplacian cofactor when a small determinant is simpler than listing the trees.

A frequent mistake is to count edge subsets of the right size and assume they are all trees. A spanning tree on \(n\) vertices has \(n-1\) edges, but that condition alone does not guarantee connectivity or the absence of cycles. For example, in the diamond graph above, the three edges \(\{12,14,24\}\) form a triangle on vertices \(1,2,4\), while vertex \(3\) is isolated. They have the correct number of edges but are not a spanning tree. A valid count must test both connectivity and acyclicity, or use a theorem whose correspondence already enforces both.

Independent checks are especially useful for small explicit graphs: compare a determinant with a direct classification, verify a recurrence with a count in the original graph, or decode the sequences counted by a Prüfer formula. Such checks can expose arithmetic errors and missed cases before a method is applied to a larger graph.

Check Your Understanding

For each question, state which method you would use and justify any count by checking that all cases are included.

Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Count its spanning trees directly.
For a connected graph and a non-loop edge \(e\), explain why trees containing \(e\) correspond to spanning trees of \(G/e\).
How many labeled trees on \(\{1,2,3,4,5\}\) have degrees \(2,2,2,1,1\)? Give the Prüfer multiset and count its distinct sequences.
In a deletion–contraction calculation, why must parallel edges created by contraction remain distinct choices?
Give an example of a three-edge subset of a four-vertex graph that is not a spanning tree, and identify whether it fails connectivity, acyclicity, or both.