The Deletion-Contraction Recurrence For Spanning Trees

Why Deletion and Contraction Split the Count

Counting spanning trees directly can be awkward: a graph may have many possible edge subsets, and it is easy to overlook one. A useful strategy is to choose an edge and divide the spanning trees into two disjoint classes: those that use the edge and those that do not. The first class is counted in a contracted graph, and the second in a graph with the edge deleted. Together they give the deletion-contraction recurrence.

All graphs in this tutorial are finite. The original examples are simple graphs, but contraction can create parallel edges, so the contracted graphs are allowed to be multigraphs. Parallel edges are distinct edge copies and must be counted separately. A spanning tree is a connected, acyclic subgraph containing every vertex. For a disconnected graph, define its spanning-tree count to be zero. Write $t(G)$ for the number of spanning trees of $G$.

Definition: Let $e=uv$ be a non-loop edge of $G$. The graph $G-e$ is obtained by deleting just $e$. The graph $G/e$ is obtained by identifying $u$ and $v$ as one vertex, keeping every other edge as a distinct edge copy with its endpoints updated. Any edge that becomes a loop is discarded, since no spanning tree can use a loop. In particular, if two edges become parallel after the identification, both are retained.

The recurrence applies to a non-loop edge, meaning an edge whose two endpoints are distinct. It does not assert that the two terms on the right are always positive: deletion can disconnect the graph, in which case its spanning-tree count is zero.

The Deletion-Contraction Theorem

Theorem: If $e$ is a non-loop edge of a finite graph $G$, then $$ t(G)=t(G-e)+t(G/e). $$ For a multigraph, parallel edges are counted as distinct edge copies.

Proof. Partition the spanning trees of $G$ into those that omit $e$ and those that contain $e$. The trees that omit $e$ are exactly the spanning trees of $G-e$: deleting $e$ changes neither their vertices nor their other edges.

Now consider a spanning tree $T$ containing $e=uv$. Contract $e$ in $T$. The result is connected and spans the contracted vertex set. It has one fewer vertex and one fewer edge than $T$. A tree on $n$ vertices has $n-1$ edges, so the contracted graph has one fewer edge than vertices and is a tree. Thus this operation gives a spanning tree of $G/e$.

Conversely, take a spanning tree $S$ of $G/e$. Replace each edge of $S$ by the particular edge copy of $G$ from which it came, separate the contracted vertex back into $u$ and $v$, and add $e$. The resulting subgraph spans $G$ and is connected: the edges of $S$ connect all contracted vertices, and $e$ joins $u$ to $v$. It has $|V(G)|-1$ edges, so it is a tree. These operations are inverse, because edge copies are tracked individually. Hence trees containing $e$ are in bijection with spanning trees of $G/e$. Adding the sizes of the two disjoint classes proves the recurrence. If $G$ has no spanning trees, both classes are empty, so the same partition argument still applies. $\square$

The edge-count fact used in the proof is elementary: a tree on $n$ vertices has $n-1$ edges, and a connected graph on $n$ vertices with $n-1$ edges is a tree. For the second statement, if a connected graph had a cycle, removing one edge of that cycle would leave it connected with only $n-2$ edges, impossible because a connected graph needs at least $n-1$ edges. The first statement follows, for example, by repeatedly removing a leaf from a tree until one vertex remains.

Worked Example: Contracting an Edge of a Triangle

Let $G$ have vertex set $V(G)=\{1,2,3\}$ and edge set $E(G)=\{12,23,13\}$. Choose $e=12$. The original graph is a triangle, and we will count its spanning trees using the recurrence.

Deleting $12$ leaves the path with edges $23$ and $13$. Both edges are required to connect all three vertices, so $t(G-12)=1$.

For contraction, identify vertices $1$ and $2$ as $x$. The edge $23$ becomes an edge from $x$ to $3$, and the edge $13$ also becomes an edge from $x$ to $3$. They are two distinct parallel edges. The contracted graph has vertex set $\{x,3\}$. A spanning tree on these two vertices must choose exactly one of the two edge copies, so $t(G/12)=2$.

Therefore the recurrence gives $t(G)=1+2=3$. Check: a spanning tree of the original triangle is obtained by omitting exactly one of its three edges, giving $3$ choices. This independent count agrees. If the two parallel edges had been collapsed into one, the contracted count would incorrectly be $1$.

Counting Parallel Edge Copies Correctly

Contraction does not mean replacing all edges between two vertices by a single edge. The recurrence counts spanning trees as choices of edge copies, so parallel edges can give different spanning trees even when they have the same endpoints. In a simple graph, parallel edges often arise when the endpoints of the contracted edge have a common neighbor: the edges from each endpoint to that neighbor become parallel.

Worked Example: A Square with a Diagonal

Let $G$ have vertex set $V(G)=\{1,2,3,4\}$ and edge set $E(G)=\{12,23,34,41,13\}$. Choose the diagonal $e=13$.

Deleting $13$ leaves the 4-cycle with edges $12,23,34,41$. A spanning tree of a cycle is obtained by removing one edge: removing any one of these four edges leaves a connected path on all four vertices. Thus $t(G-13)=4$.

For contraction, identify $1$ and $3$ as $x$. The edge copies $12$ and $23$ become two distinct edges from $x$ to $2$; the copies $14$ and $34$ become two distinct edges from $x$ to $4$. The contracted graph has vertex set $\{x,2,4\}$ and these four edge copies, with two parallel copies between $x$ and $2$, and two between $x$ and $4$. A spanning tree must choose one edge from each pair: choosing both copies in one pair and neither in the other would leave a vertex isolated, while choosing both pairs’ edges would make a cycle. Hence $t(G/13)=2\cdot2=4$, and the recurrence gives $t(G)=4+4=8$.

Check: count directly in $G$. Trees omitting $13$ are the four paths obtained by deleting one cycle edge. For a tree containing $13$, vertex $2$ must be connected using either $12$ or $23$, and vertex $4$ using either $14$ or $34$. These choices give $2\cdot2=4$ trees containing $13$. The two classes total $4+4=8$, as before.

When Deletion Disconnects the Graph

An edge $e$ of a connected graph is a bridge if deleting it disconnects the graph. Every spanning tree must contain a bridge: if a spanning tree omitted it, that tree would still connect every vertex after the bridge was deleted, contradicting that deletion disconnects the graph. The recurrence therefore has a particularly simple interpretation for a bridge: the deletion term is zero, and the count is given by the contracted graph.

Corollary: If $G$ is connected and $e$ is a bridge, then $t(G-e)=0$ and $t(G)=t(G/e)$.

Proof. By definition, $G-e$ is disconnected, so $t(G-e)=0$. Substituting this into the deletion-contraction recurrence gives $t(G)=0+t(G/e)=t(G/e)$. $\square$

Worked Example: A Bridge Attached to a Triangle

Let $G$ have vertex set $V(G)=\{1,2,3,4,5\}$ and edge set $E(G)=\{12,23,31,34,45\}$. Choose $e=34$. This edge is a bridge: deleting it separates $\{1,2,3\}$ from $\{4,5\}$.

Since $G-34$ is disconnected, $t(G-34)=0$. Contract $34$ to a vertex $x$. The contracted graph has vertex set $\{1,2,3,x\}$ and edge set $\{12,23,31,x5\}$. It is a triangle with a pendant edge $x5$. Every spanning tree must use $x5$, and among the three triangle edges it must use exactly two. Omitting any one triangle edge leaves a connected path on $1,2,3$, so there are $3$ choices. Thus $t(G/34)=3$, and the recurrence gives $t(G)=0+3=3$.

Check: directly in $G$, the bridge $34$ and the edge $45$ must both be included. The triangle on $\{1,2,3\}$ contributes exactly two of its three edges, giving $3$ choices. Therefore $t(G)=3$, agreeing with the recurrence.

Using the Recurrence Reliably

For a hand calculation, the main decisions are which edge to choose and how to represent its contraction. The recurrence is an identity, so any non-loop edge is valid. An edge is often useful if deleting it simplifies the graph, if contracting it creates a graph whose count is already known, or if it is a bridge and the deletion term vanishes. After contraction, record the new vertex set and list every surviving edge copy. This prevents a common counting error: treating parallel edges as one.

The two terms have different meanings. The count $t(G-e)$ includes precisely the trees that avoid the chosen edge; $t(G/e)$ counts precisely the trees that use it, with the chosen edge represented by the identification of its endpoints. The terms are added, not multiplied, because they are disjoint cases. Within a contracted graph, choices among parallel copies may produce a product when each pair of choices is independent, as in the square-with-diagonal example.

Common mistake. In the triangle example, one might contract $12$, see just one pair of vertices, and write $t(G/12)=1$ by treating the two resulting edges as a single edge. This loses the distinction between the original edges $13$ and $23$: either copy can be selected, so there are two spanning trees of the contracted multigraph. The correct calculation is $t(G)=1+2=3$, not $1+1=2$.

Another useful check is to count the original trees by the same two cases used in the proof. If the sum from the recurrence does not match that independent partition on a small graph, inspect whether a parallel edge copy was lost or whether an edge set fails to connect all vertices.

Check Your Understanding

For each question, keep distinct parallel edge copies distinct whenever contraction creates them.

Let $G$ have vertices $\{1,2,3,4\}$ and edges $\{12,23,34,41,13\}$. Apply the recurrence using edge $12$, and describe the parallel edges in $G/12$.
Explain why spanning trees that contain a chosen edge correspond to spanning trees of the contracted graph.
In the square-with-diagonal example, what incorrect count would result if each pair of parallel edges were collapsed to one edge?
Let $G$ be connected and let $e$ be a bridge. Explain why $t(G-e)=0$ and use the recurrence to state $t(G)$ in terms of $G/e$.
Give an example of a non-loop edge whose deletion disconnects a graph, and identify which term of the recurrence is zero.