From Spanning Trees to Edge Subsets
A spanning tree keeps every vertex of a connected graph while discarding enough edges to remove all cycles. For a small labeled graph, one can count its spanning trees directly: determine the required size of a candidate edge set, list the candidates, and test each for connectivity and acyclicity. Organizing the list by omitted edges often makes the work shorter and easier to check.
All graphs in this tutorial are finite and simple. A candidate spanning subgraph is specified by an edge subset \(F\subseteq E\), with the full vertex set \(V\) retained. An omitted-edge set is \(R=E\setminus F\). If \(G\) has \(n\ge1\) vertices and \(m\) edges, every spanning tree has \(n-1\) edges, so a candidate must omit exactly \(m-(n-1)\) edges. If this number is negative, there are too few edges for a spanning tree.
Proof. A tree on one vertex has zero edges, which equals \(1-1\). Suppose \(n>1\). A finite tree has a leaf: for example, an endpoint of a longest path cannot have another neighbor outside the path, and it cannot have a second neighbor on the path without creating a cycle. Delete a leaf and its single incident edge. The remaining graph is still connected, since a leaf cannot be an internal vertex of a path between two remaining vertices, and it is still acyclic, since deleting vertices and edges cannot create a cycle. Thus it is a tree on \(n-1\) vertices. Induction gives it \(n-2\) edges, so the original tree had \(n-1\) edges. For the enumeration statement, a spanning tree is, by definition, connected and acyclic on all vertices; by the edge count just proved, it appears among the \(n-1\)-edge subsets. Conversely, any such subset that is connected and acyclic is a spanning tree by the definition. \(\square\)
The edge count is a filter, not a test for being a tree. An \(n-1\)-edge subgraph can still be disconnected and contain a cycle at the same time. Both properties must be checked. In a small example, connectivity can be checked by following the edges from a chosen vertex and confirming that every vertex is reached; acyclicity can be checked by looking for a cycle in the selected edges.
Worked Counts by Omitted Edges
Worked Example: Spanning Trees of a 4-Cycle
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). It has \(n=4\) vertices and \(m=4\) edges. A spanning tree must have \(n-1=3\) edges, so it must omit \(4-3=1\) edge. The four possible omitted-edge sets and the corresponding retained edges are:
| Omitted edge | Retained edges | Result |
|---|---|---|
| \(12\) | \(23,34,41\) | Path \(2,3,4,1\): a tree |
| \(23\) | \(12,34,41\) | Path \(2,1,4,3\): a tree |
| \(34\) | \(12,23,41\) | Path \(3,2,1,4\): a tree |
| \(41\) | \(12,23,34\) | Path \(1,2,3,4\): a tree |
Each retained set has three edges, reaches all four vertices in the displayed path, and has no cycle. Thus all four candidates are spanning trees, and \(t(G)=4\). As a check by structure, a spanning subgraph of this cycle becomes connected and acyclic when any one cycle edge is removed; removing no edges leaves a cycle, while removing two or more edges leaves at most two edges and cannot connect all four vertices.
Worked Example: Two Triangles Sharing a Vertex
Let \(G\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,13,23,34,45,35\}\). For clarity, name the edges \(a=12\), \(b=13\), \(c=23\), \(d=34\), \(e=45\), and \(f=35\). The triangles are \(1,2,3,1\) and \(3,4,5,3\). A spanning tree has \(5-1=4\) edges, so it omits two of the six edges. There are \(\binom{6}{2}=15\) possible omitted pairs.
If both omitted edges lie in the first triangle, the second triangle remains intact and gives a cycle; the same reasoning applies with the triangles reversed. These are the six within-triangle pairs: \(ab,ac,bc,de,df,ef\). The other nine pairs omit one edge from each triangle. For each such pair, the two retained edges in each triangle form a path joining all three of that triangle’s vertices to the shared vertex \(3\). The two paths meet at \(3\), so their union is connected and has no cycle. The full classification is:
| Omitted pairs | Number | Test |
|---|---|---|
| \(ab,ac,de,ef\) | 4 | Fail: one vertex is isolated and the other triangle remains a cycle |
| \(bc,df\) | 2 | Fail: the other triangle remains a cycle |
| \(ad,ae,af,bd,be,bf,cd,ce,cf\) | 9 | Pass: connected and acyclic |
For the four pairs \(ab,ac,de,ef\), the sole retained edge in the triangle with two omissions isolates the vertex opposite that edge: \(ab\) leaves \(c=23\) and isolates \(1\); \(ac\) leaves \(b=13\) and isolates \(2\); \(de\) leaves \(f=35\) and isolates \(4\); \(ef\) leaves \(d=34\) and isolates \(5\). For \(bc\), the sole retained edge in the first triangle is \(a=12\), and its opposite vertex \(3\) remains connected to the other triangle. For \(df\), the sole retained edge in the second triangle is \(e=45\), and its opposite vertex \(3\) remains connected to the first triangle. Those two candidates still fail because the other triangle remains a cycle.
Therefore exactly the nine cross-triangle omission pairs give spanning trees, so \(t(G)=9\). Check the count independently by choosing which two edges to retain in each triangle: there are three choices of two edges from \(\{a,b,c\}\) and three from \(\{d,e,f\}\). Every pair of choices gives the connected, acyclic union described above, and every valid candidate has exactly one such pair of choices. Hence the count is \(3\cdot3=9\).
Worked Example: \(K_4\) with One Edge Deleted
Let \(G\) have \(V=\{1,2,3,4\}\) and \(E=\{12,13,14,23,34\}\), which is \(K_4\) with edge \(24\) deleted. Name the edges \(a=12\), \(b=13\), \(c=14\), \(d=23\), and \(e=34\). A spanning tree has three edges, so we omit two. The \(\binom{5}{2}=10\) omitted pairs yield the following retained triples:
| Omitted pair | Retained edges | Result |
|---|---|---|
| \(ab\) | \(c,d,e\) | Tree: path \(1,4,3,2\) |
| \(ac\) | \(b,d,e\) | Tree: edges \(13,23,34\) |
| \(ad\) | \(b,c,e\) | Fail: triangle \(1,3,4,1\); vertex \(2\) isolated |
| \(ae\) | \(b,c,d\) | Tree: edges \(13,14,23\) |
| \(bc\) | \(a,d,e\) | Tree: path \(1,2,3,4\) |
| \(bd\) | \(a,c,e\) | Tree: path \(2,1,4,3\) |
| \(be\) | \(a,c,d\) | Tree: edges \(12,14,23\) |
| \(cd\) | \(a,b,e\) | Tree: path \(2,1,3,4\) |
| \(ce\) | \(a,b,d\) | Fail: triangle \(1,2,3,1\); vertex \(4\) isolated |
| \(de\) | \(a,b,c\) | Tree: star with center \(1\) |
In each row labeled “Tree,” the three listed edges connect all four vertices and contain no cycle. In each failing row, the three selected edges form a triangle and leave the fourth vertex isolated. Thus eight of the ten candidates are spanning trees, giving \(t(G)=8\). As a count check, the table identifies exactly two failures among ten candidates, and \(10-2=8\). Listing the eight passing triples directly gives the same count: there are eight rows marked “Tree.”
Why the Tests Must Be Used Together
For a candidate on \(n\) vertices with \(n-1\) edges, connectivity and acyclicity are equivalent tests for being a tree, but checking both is a reliable way to audit a direct enumeration. The standard tree fact behind the equivalence is that a tree has \(n-1\) edges: if an \(n-1\)-edge graph is connected, it cannot contain a cycle, since deleting an edge of that cycle would leave it connected with fewer than \(n-1\) edges. If an \(n-1\)-edge graph is acyclic, it has exactly one connected component, since a forest on \(n\) vertices with \(k\) components has \(n-k\) edges. These tree and forest edge counts are standard results from the earlier material on trees.
Direct enumeration is most useful when the number of candidate subsets is small enough to inspect carefully. If \(m\ge n-1\), the number of candidates to check is \(\binom{m}{n-1}\), or equivalently \(\binom{m}{m-n+1}\) when listing omitted edges. For a graph with too many candidates, more structured counting methods may be preferable; the point here is to make a hand count auditable rather than to claim that brute force is always efficient.
Common Pitfall: Counting the Right-Sized Sets as Trees
A common error is to count every edge subset of size \(n-1\) as a spanning tree. In the \(K_4\)-minus-\(24\) example, the three-edge set \(\{12,13,23\}\) has the required size \(4-1=3\), but it is a triangle on vertices \(1,2,3\), while vertex \(4\) is isolated. It is not connected and is not a spanning tree. The correction is to use the edge count only to generate candidates, then test connectivity and acyclicity. In this example, precisely the omitted pairs \(ce\) and \(ad\) produce such failures, so they must be excluded.
Keep the graph’s full vertex set in every candidate, including vertices that become isolated after edges are omitted. Otherwise a disconnected candidate can be mistakenly treated as a tree on fewer vertices. Also handle the boundary cases explicitly: the single-vertex graph has one spanning tree, and any disconnected graph with at least one vertex has none.
Check Your Understanding
For each question, specify the vertex set and edge set of any graph you use, then justify the count by checking the candidates.
- For \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41,13\}\), how many edges must a spanning tree contain, and how many edges must it omit?
- Explain why a three-edge subset of the edges of \(K_4\) need not be a spanning tree.
- In the two-triangles example, why do all nine omitted pairs with one omission from each triangle give connected, acyclic subgraphs?
- How many spanning trees does the graph with one vertex and no edges have under the convention used here?
- Why does a disconnected graph have no spanning tree, regardless of whether some component contains a cycle-free spanning subgraph of that component?