"How many spanning trees does this graph have?" is a question students either finish quickly or turn into a page of drawings. The difference is recognising the graph and choosing the right counting tool.
You need two main methods: Cayley's formula for a complete graph, and deletion-contraction for a graph that is not complete. Cayley's formula applies to complete graphs, while deletion-contraction handles non-complete graphs; the Matrix-Tree theorem independently verifies the result.
1. What a spanning tree is and what "count them" means
A spanning tree of a connected graph contains every vertex, remains connected and has no cycle. If the graph has V vertices, every spanning tree has exactly V - 1 edges.
Counting spanning trees means counting the valid edge subsets, not constructing a minimum-cost tree. The count is commonly written as tau(G). Edge weights are irrelevant unless a separate question asks about minimum spanning trees.
Three facts save time:
A tree on
Vvertices hasV - 1edges.Every bridge of the graph must occur in every spanning tree.
An edge on a cycle may be omitted while connectivity can still survive.
A cut vertex can also simplify the picture because tree choices in blocks attached at that vertex can often be counted separately. Before applying a formula, inspect the graph for complete pieces, cycles, bridges and repeated structure.
For the broader vocabulary of paths, cycles and connectivity, revise Graph Theory: Euler and Hamiltonian Paths, Coloring and Connectivity first.
2. Cayley's formula for complete graphs
The complete graph K_n has an edge between every pair of its n labelled vertices. Cayley's formula says:
tau(K_n) = n^(n - 2)
So the small values are immediate:
K_3:3^(3 - 2) = 3^1 = 3K_4:4^(4 - 2) = 4^2 = 16K_5:5^(5 - 2) = 5^3 = 125
This is also the number of labelled trees on n vertices. "Labelled" matters. Relabelling a vertex can produce a different labelled tree even when the drawing has the same shape.
The formula's boundary is just as important as the formula. Cayley applies to K_n, not to every graph with n vertices. If even one edge is missing, n^(n - 2) is no longer the direct answer.
3. Deletion-contraction: the tool for non-complete graphs
Choose an edge e. Every spanning tree either avoids e or uses e, and the two cases cannot overlap. Therefore:
tau(G) = tau(G - e) + tau(G / e)
G - e is the graph after deleting the edge. It counts the spanning trees that avoid e. G / e is the graph after contracting the edge, which merges its endpoints. It counts the spanning trees that use e because that chosen edge has already joined its endpoints.
Contraction has two bookkeeping rules:
Keep parallel edges. They represent different original edge choices and must be counted separately.
Ignore self-loops. A self-loop cannot belong to a tree because it creates a cycle without connecting a new vertex.
Apply the recurrence until the remaining graphs are easy. A tree has one spanning tree, itself. A cycle C_k has k spanning trees because deleting any one of its k edges produces a path through all vertices.
4. Worked example: the diamond graph
Take vertices 1, 2, 3, 4 with edges 12, 23, 34, 41 and diagonal 13. This is a four-cycle plus one diagonal. It is also K_4 with edge 24 removed.
Choose e = 13 for deletion-contraction.
Deletion case. Removing 13 leaves the cycle 1-2-3-4-1. A four-cycle has four spanning trees, one for each choice of the edge to drop. Thus tau(G - 13) = 4.
Contraction case. Contract 13 and call the merged vertex x. Edges 12 and 23 become two parallel edges between x and 2. Edges 34 and 41 become two parallel edges between x and 4. There is no edge from 2 to 4.
A spanning tree of this three-vertex multigraph must be the path 2-x-4. Choose one of the two x-2 edges and one of the two x-4 edges:
tau(G / 13) = 2 x 2 = 4
Now add the disjoint cases:
tau(G) = tau(G - 13) + tau(G / 13) = 4 + 4 = 8
Notice why parallel edges matter. Replacing each pair by one edge would incorrectly turn the contracted graph into a single path and give only one tree instead of four.
5. Cross-check with the Matrix-Tree theorem
Kirchhoff's Matrix-Tree theorem says that tau(G) equals any cofactor of the graph Laplacian L = D - A. The diagonal contains vertex degrees, and an off-diagonal entry is -1 when the corresponding vertices are adjacent.
For the diamond, the degrees of vertices 1, 2, 3, 4 are 3, 2, 3, 2. Delete row 4 and column 4 from the Laplacian. The remaining matrix is:
1 | 2 | 3 | |
|---|---|---|---|
1 | 3 | -1 | -1 |
2 | -1 | 2 | -1 |
3 | -1 | -1 | 3 |
Expanding its determinant along the first row gives:
3[(2)(3) - (-1)(-1)] + [(-1)(3) - (-1)(-1)] - [(-1)(-1) - (2)(-1)]
= 3(5) + (-4) - 3
= 15 - 4 - 3 = 8
That independently matches deletion-contraction. There is another quick check. K_4 has 16 spanning trees, and each tree uses three edges, so there are 16 x 3 = 48 edge appearances across all trees. The six edges of K_4 are symmetric, so each appears in 48 / 6 = 8 trees. Removing edge 24 removes those eight trees and leaves 16 - 8 = 8.
For more systematic treatment of the underlying results, use the Engineering Mathematics course.
6. The traps GATE builds these on
Applying Cayley to a graph that is not complete.
Deleting parallel edges created by contraction.
Keeping a self-loop as a tree edge.
Forgetting that a cycle
C_khask, notk - 1, spanning trees.Confusing a spanning-tree count with the number or total weight of minimum spanning trees.
If the question introduces edge weights, pause and identify the target. The methods here count all spanning trees. The Minimum Spanning Tree for GATE: Kruskal and Prim Numericals with Unique-MST Questions covers the optimisation problem.
7. How GATE tests this and the official pointer
Typical prompts ask for tau(K_n), the number of labelled trees, or the count for a small graph that simplifies under deletion-contraction. A small determinant may also appear as a Matrix-Tree application.
KnowledgeGate has more than 1,300 Discrete Mathematics questions, including graph-theory counting practice for this topic. Use that pool to meet the same method in different drawings instead of memorising one diamond.
Spanning-tree counting belongs to the graph-theory part of Discrete Mathematics. Its exact place and any cycle-specific paper details come from the current official GATE portal, not a remembered weightage figure. The GATE category provides the wider preparation context.
8. The short version and your next step
For a complete graph, use tau(K_n) = n^(n - 2). For a non-complete graph, split on an edge with tau(G) = tau(G - e) + tau(G / e), keep parallel edges and discard self-loops.
Rework the diamond until 4 + 4 = 8 feels inevitable, then attempt timed graph-theory sets in the GATE Test Series. Count by structure first and use a Laplacian cofactor to check small cases.
