Choosing a Counting Method
A spanning-tree count can be approached in several ways, and the most efficient method depends on the graph’s structure. For a small graph, enumerating edge subsets may be quickest. Degree constraints on labeled trees suggest Prüfer codes. An edge whose deletion or contraction simplifies the graph suggests deletion–contraction. Symmetry can group equivalent cases, while a Laplacian cofactor gives a systematic calculation for a connected graph.
These methods are not interchangeable without regard to their hypotheses. Prüfer codes count labeled trees on a complete vertex set, so additional restrictions on which edges are allowed must still be enforced. Deletion–contraction applies to a non-loop edge, and contraction can create parallel edges. The matrix-tree theorem applies to a graph’s Laplacian cofactor. The goal is to choose a method whose structure matches the graph, then check the result by an independent count whenever possible.
All graphs in the examples are finite. Unless stated otherwise, graphs are simple. During contraction we allow parallel edges and count them as distinct edges; loops can be discarded because they cannot belong to a tree.
Direct Enumeration and Prüfer Codes
Direct enumeration is attractive when the graph is small and the possible spanning edge sets are few. If \(G\) has \(n\) vertices, each candidate must have exactly \(n-1\) edges. Check that it connects all vertices and has no cycle. For a candidate with \(n-1\) edges on \(n\) vertices, it is also enough to check connectedness: a connected graph on \(n\) vertices with \(n-1\) edges is a tree.
Prüfer codes are useful when the object being counted is a labeled tree on a fixed vertex set, especially when degrees are specified. A labeled tree on \(n\) vertices has a Prüfer sequence of length \(n-2\), and the degree of each label is one plus the number of its occurrences in the sequence. The correspondence between labeled trees and sequences is one-to-one. These standard facts from the earlier material on Prüfer codes explain why counting sequences counts trees; for an arbitrary graph, however, one must also ensure that each tree edge is allowed by the graph.
Worked Example: Directly Count a Graph with Two Triangles
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,23,14,34\}\). Count its spanning trees by direct enumeration.
There are four vertices, so each spanning tree must have \(4-1=3\) edges. The graph has five edges, giving \(\binom{5}{3}=10\) three-edge subsets to check. Two subsets are triangles: \(\{12,13,23\}\) and \(\{13,14,34\}\). Neither is spanning, because each leaves one vertex isolated.
The other eight three-edge subsets are spanning trees. To verify that no other subset fails, a disconnected three-edge subgraph on four vertices must either contain a triangle and an isolated vertex, or have components on two vertices each. The second possibility has at most two edges in a simple graph. Thus only the two listed triangles fail, and \(t(G)=10-2=8\).
Check: the degree sequence of \(G\) is \(3,2,3,2\), so the Laplacian cofactor obtained by deleting row and column \(4\) is \(\begin{pmatrix}3&-1&-1\\-1&2&-1\\-1&-1&3\end{pmatrix}\). Its determinant is \(3(6-1)-(-1)(-4)+(-1)(3)=15-4-3=8\), confirming the direct count.
Worked Example: Prüfer Codes with Prescribed Degrees
Take the complete graph \(K_5\), explicitly \(V=\{1,2,3,4,5\}\) and \(E=\{ij:1\le i<j\le5\}\). Count its spanning trees having degrees \(\deg(1)=3\), \(\deg(2)=2\), and \(\deg(3)=\deg(4)=\deg(5)=1\).
A Prüfer sequence for a tree on five labels has length \(5-2=3\). The required occurrence counts are degree minus one: label \(1\) must appear twice, label \(2\) once, and labels \(3,4,5\) not at all. The possible sequences are exactly \(112,121,211\), so the code correspondence gives three trees.
For example, decoding \(121\) removes the smallest label absent from the remaining code at each step. First \(3\) is absent, so add \(31\); then \(4\) is absent, so add \(42\); then \(2\) is absent, so add \(21\); the final two labels give \(15\). The resulting edges are \(\{13,42,21,15\}\), with degrees \(3,2,1,1,1\), as required. The same degree check follows for each of the other two sequences because their occurrence counts are identical.
Check: there are three distinct arrangements of the multiset \(\{1,1,2\}\), namely \(3!/2!=3\). Each sequence decodes to a distinct labeled tree, and every tree with the specified degrees has one of these codes. Hence the count is exactly \(3\).
Deletion–Contraction and Symmetry
Proof. Partition the spanning trees of \(G\) into those that omit \(e\) and those that contain \(e\). A spanning tree omitting \(e\) is exactly a spanning tree of \(G-e\): it still uses all vertices, and its connectedness and absence of cycles are unchanged. A spanning tree containing \(e\), after contracting \(e\), becomes a spanning tree of \(G/e\). Conversely, expanding the contracted vertex in a spanning tree of \(G/e\) and adding \(e\) gives a spanning tree of \(G\) that contains \(e\). These operations are inverse; retaining parallel edges keeps distinct choices distinct. The two classes are disjoint and exhaust all spanning trees, so their counts add as stated. \(\square\)
This recurrence can be effective when both smaller graphs are easy to count. It can be inefficient if successive deletions and contractions produce many different graphs. The non-loop condition matters: a loop cannot belong to a spanning tree, so deleting a loop leaves \(t(G)\) unchanged rather than splitting the count into two equal terms.
Worked Example: Apply Deletion–Contraction to the Two-Triangle Graph
Use the graph \(G\) from the first example, with \(V=\{1,2,3,4\}\), \(E=\{12,13,23,14,34\}\), and choose \(e=12\). The edge is not a loop, so the recurrence applies.
In \(G-12\), the edges are \(\{13,23,14,34\}\). They form a triangle on \(1,3,4\) with the pendant edge \(23\). The pendant edge must be included, and two of the three triangle edges must be chosen. Thus \(t(G-12)=3\).
In \(G/12\), identify \(1\) and \(2\) as a vertex \(x\). The resulting vertices are \(x,3,4\), and the edges are two distinct parallel edges \(x3\), together with \(x4\) and \(34\). A spanning tree needs two edges. Of the six pairs of distinct edges, the pair consisting of the two parallel \(x3\) edges does not connect \(4\). The other five pairs do connect all three vertices. Hence \(t(G/12)=5\), and the recurrence gives \(t(G)=3+5=8\).
Check: the direct count above found eight spanning trees by checking the \(\binom{5}{3}=10\) three-edge subsets and excluding the two triangles. This agrees with \(3+5=8\).
Symmetry helps when graph automorphisms make edges or vertices equivalent. A graph automorphism is a relabeling of vertices that preserves adjacency. If every edge can be mapped to every other edge by an automorphism, then each edge belongs to the same number of spanning trees: applying such a relabeling gives a bijection between the relevant sets of trees.
Proof. Count the incidences by first choosing a spanning tree. Each spanning tree on \(n\) vertices has \(n-1\) edges, so there are \((n-1)t(G)\) incidences. If all \(m\) edges are equivalent, the automorphism bijections show that each edge occurs equally often. The sum of those \(m\) equal occurrence counts is \((n-1)t(G)\), so each is \((n-1)t(G)/m\). If there are no spanning trees, both the incidence count and each occurrence count are zero. \(\square\)
Worked Example: Use Symmetry to Organize the Cycle Count
Let \(G=C_5\), with \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). Each spanning tree must have four edges. Omitting any one of the five edges leaves a path through all five vertices, hence a spanning tree. Omitting two edges leaves only three edges, which cannot be a spanning tree. Therefore there are exactly five spanning trees.
Rotations of the cycle map any edge to any other edge, so symmetry says each edge occurs in the same number of spanning trees. The incidence count is \((5-1)t(G)=4\cdot5=20\); divided equally among five edges, each edge appears in \(20/5=4\) trees. This agrees with the direct description: a given edge is present in every spanning tree except the one formed by omitting it.
Check: the five spanning trees are indexed by their omitted edges, one for each member of \(E\). Each has four edges, so the total edge-tree incidences are \(5\cdot4=20\), as the symmetry calculation requires.
When a Laplacian Cofactor Is the Better Choice
The matrix-tree theorem is often the most systematic option when a graph is too large for direct enumeration and has no convenient code or recurrence. For a connected graph, form its Laplacian \(\mathbf L=\mathbf D-\mathbf A\), where \(\mathbf D\) has vertex degrees on its diagonal and \(\mathbf A\) is the adjacency matrix. The matrix-tree theorem states that deleting any one row and the corresponding column from \(\mathbf L\) gives a matrix whose determinant is \(t(G)\). This standard theorem, including its proof, was established in the earlier material on the matrix-tree theorem.
For a graph with parallel edges, the Laplacian entries count edge multiplicities. A cofactor computation is exact but may be algebraically longer than a short structural count. It is especially useful as an independent check on direct enumeration or deletion–contraction, as the first example illustrated.
A Practical Selection Guide
| Method | Good fit | Condition or caution |
|---|---|---|
| Direct enumeration | Small graph; few subsets of size \(n-1\) | Check both spanning and acyclic; do not count subsets of the wrong size. |
| Prüfer codes | Labeled trees with degree restrictions | Codes count trees on the complete label set; enforce allowed-edge restrictions if present. |
| Deletion–contraction | An edge whose deletion and contraction simplify the graph | Use a non-loop edge; retain distinct parallel edges after contraction. |
| Symmetry | Automorphisms group equivalent edges or cases | Symmetry can equate counts but does not usually determine the total by itself. |
| Matrix-tree theorem | A direct exact computation for a connected graph | Compute a Laplacian cofactor; use another method to check arithmetic when feasible. |
Common pitfall. A spanning tree on four vertices has three edges, not four. For the graph with \(E=\{12,13,23,14,34\}\), counting four-edge subsets cannot count spanning trees: each such subset has too many edges to be acyclic and connected. The correct candidates are the \(\binom{5}{3}=10\) three-edge subsets, of which exactly two are triangles and the remaining eight are spanning trees. A second caution is to count a triangle with a pendant edge correctly: its pendant edge is forced, while any two of the three triangle edges may be chosen, giving three spanning trees—not one.
Check Your Understanding
For each question, state the method you would use and justify its applicability.
- A simple graph has five vertices and seven edges. How many edges must each candidate spanning tree contain?
- For a labeled tree on six vertices with degree sequence \((3,2,2,1,1,1)\), what are the required Prüfer-code occurrence counts, and how many sequences have those counts?
- Why does deletion–contraction need to exclude a loop, and what should be done with loops when counting spanning trees?
- If a graph has eight edges and is edge-transitive, and its spanning-tree count is \(t(G)=14\) on five vertices, how many spanning trees contain each edge?
- Give one reason a Laplacian cofactor may be preferable to direct enumeration, and one reason an independent check is still useful.