Using Graph Symmetry To Count Spanning Trees

Symmetry as a Counting Tool

A graph may have many spanning trees, but its symmetries can make those trees fall into a small number of classes. Instead of listing every spanning tree separately, we can group trees that are carried into one another by a symmetry of the graph, count the members of each class, and add those counts. The essential caution is that different classes can have different sizes: counting classes alone does not count spanning trees.

All graphs in this tutorial are finite and simple unless a contraction is explicitly discussed. A spanning tree of a connected graph \(G\) is a subgraph with vertex set \(V(G)\) that is connected and has no cycles. Write \(t(G)\) for the number of spanning trees of \(G\). For a connected graph with one vertex, \(t(G)=1\), since the graph with that vertex and no edges is its only spanning tree.

Automorphisms preserve the properties that define a spanning tree: they preserve adjacency, connectivity, and cycles. Thus the action really does send a spanning-tree candidate to another spanning tree. If the automorphisms split the spanning trees into orbits \(O_1,\dots,O_r\), then each spanning tree belongs to exactly one orbit, so

Orbit Sizes and Edge Symmetry

Proof. Let \(\Gamma\) be the group and let \(\Gamma_x=\{\varphi\in\Gamma:\varphi(x)=x\}\) be the stabilizer of \(x\). Two group elements \(\varphi,\psi\) send \(x\) to the same object exactly when \(\psi^{-1}\varphi\in\Gamma_x\): applying \(\psi^{-1}\) to \(\varphi(x)=\psi(x)\) gives this condition, and reversing the steps proves the converse. Consequently, the group elements that send \(x\) to any one object in its orbit form a coset of \(\Gamma_x\), with \(|\Gamma_x|\) elements. These cosets partition \(\Gamma\), one for each object in the orbit. Therefore \(|\Gamma|=|O(x)|\,|\Gamma_x|\), giving \(|O(x)|=|\Gamma|/|\Gamma_x|\). \(\square\)

A graph is edge-transitive if, for every pair of edges, some automorphism sends one edge to the other. This property gives a useful count even when it does not directly give the total number of spanning trees.

Proof. For each edge \(e\), let \(a_e\) be the number of spanning trees containing \(e\). If an automorphism sends \(e\) to \(f\), applying it to each spanning tree gives a bijection between the trees containing \(e\) and those containing \(f\). Edge-transitivity therefore makes all the numbers \(a_e\) equal, say to \(a\). Count pairs \((T,e)\) where \(T\) is a spanning tree and \(e\) is one of its edges. Each spanning tree on \(n\) vertices has \(n-1\) edges, so there are \(t(G)(n-1)\) pairs. Counting instead by the edge gives \(ma\) pairs. Thus \(ma=t(G)(n-1)\), and \(a=t(G)(n-1)/m\). \(\square\)

The theorem uses the standard fact that a tree on \(n\) vertices has \(n-1\) edges, established in the earlier material on trees. The hypothesis \(n\ge2\) ensures that a connected graph has edges, so \(m\) is nonzero. Edge-transitivity equalizes the counts for individual edges; it does not by itself determine \(t(G)\).

Symmetry Does Not Mean One Orbit

The complete graph \(K_4\) has every permutation of its four vertices as an automorphism. That is a large amount of symmetry, but its spanning trees do not all lie in one orbit: a star and a path have different degree sequences, which an automorphism cannot change. The way to count is to classify the possible tree shapes and then count each orbit.

Classifying Trees in a Symmetric Bipartite Graph

For some graphs, a useful first step is to examine degrees within the spanning tree. Structural constraints can reduce the candidates to a few forms; symmetries then count how many choices realize each form.

A Useful Reduction: Deletion and Contraction

Symmetry can also reduce a calculation by making several edge choices equivalent. The basic counting identity behind this approach separates spanning trees according to whether they contain a chosen edge. When contracting an edge, parallel edges are retained as distinct edges, and loops are discarded; this convention preserves the distinction between different edge choices in a spanning tree.

Proof. Partition the spanning trees of \(G\) into those that omit \(e\) and those that contain \(e\). A tree in the first class is exactly a spanning tree of \(G-e\), so that class has size \(t(G-e)\), including zero if \(G-e\) is disconnected. For a tree in the second class, contract \(e\). The result is connected and has no cycle: a cycle after contraction would expand to a cycle in the original tree. It is therefore a spanning tree of \(G/e\). Conversely, expanding the contracted vertex in a spanning tree of \(G/e\) and restoring \(e\) gives a spanning tree of \(G\) containing \(e\). These operations are inverse, with parallel edges distinguished so that each choice is retained. The second class has size \(t(G/e)\), proving the identity. \(\square\)

If several edges are equivalent under automorphisms, the deletion-and-contraction cases for those edges have matching counts. This can cut down repeated work. It does not justify replacing several distinct cases by one unless the cases are related by an automorphism, or have otherwise been shown to have equal counts.

Common Pitfall: Counting Orbits Instead of Trees

A symmetry class is not necessarily a single spanning tree. In the \(K_4\) example, there are two orbits, but their sizes are \(4\) and \(12\). Saying “there are two types, so there are two spanning trees” is incorrect. The correct count sums the sizes of the orbits. The orbit-stabilizer calculation provides one way to find each size; direct enumeration, as in the examples, provides another.

Likewise, symmetry of the original graph does not guarantee that every spanning tree can be transformed into every other spanning tree. In \(K_4\), an automorphism preserves vertex degrees, so it cannot carry a star to a path. Before using a single orbit count, verify that the relevant action is transitive on the objects being counted.