Let \(G\) be a graph, or digraph, and let \(P=\{P_1,\dots,P_k\}\) be a partition of its vertex set. We solve the following problem: find the generating function, in the edge variables of \(G\), of the spanning trees of \(G\) each of whose restrictions to every part \(P_i\) is a spanning tree of the induced subgraph \(G[P_i]\); and, in the directed case with a fixed root \(v_i\in P_i\) for each \(i\), of the spanning arbors of \(G\) rooted at \(v_1\) each of whose restrictions to \(P_i\) is a spanning arbor of \(G[P_i]\) rooted at \(v_i\). We show that both generating functions factor as a product of the local generating functions on the parts \(G[P_i]\) (or \(P_i\), in the digraph case) with the generating function of spanning trees/arbors of a naturally associated contracted multigraph whose vertices are the parts of \(P\). This localizes the classical theorems of Kirchhoff and Tutte and yields an exact identity, and a family of lower bounds, for the number of spanning trees of \(G\) in terms of spanning-tree counts of smaller induced subgraphs.
We refer to [5] and [7] for general terminology and for proofs of the matrix-tree theorems of Kirchhoff and Tutte. A digraph is a graph with directed edges; a graph is a digraph in which \((v_i,v_j)\) is an edge if and only if \((v_j,v_i)\) is an edge. A tree is a connected, cycle-free undirected graph; it is a tree of a graph \(\Gamma\) if its edges are edges of \(\Gamma\), and a spanning tree of \(\Gamma\) if in addition it has every vertex of \(\Gamma\). A forest is a disjoint union of trees, and a spanning forest of \(\Gamma\) is a forest of \(\Gamma\) containing every vertex of \(\Gamma\). An arbor rooted at \(v\) is, after forgetting edge directions, a tree in which every edge points toward \(v\); an arborescence rooted at \(v_1,\dots,v_k\) is a disjoint union of arbors rooted, respectively, at \(v_1,\dots,v_k\). The notions of arbor, arborescence, spanning arbor and spanning arborescence of a digraph \(\Gamma\) are defined exactly as for the undirected case, see [6].
Kirchhoff’s theorem and Tutte’s theorem express the generating function of all spanning trees (respectively, spanning arbors rooted at a fixed vertex) of a graph as a single determinant of a reduced Laplacian. This paper answers the following localized version of that question.
Problem 1.1. Let \(G\) be a graph (or digraph) and let \(P=\{P_1,\dots,P_k\}\) be a partition of its vertex set into the vertex sets of the induced subgraphs \(G[P_1],\dots,G[P_k]\). Find the generating function of the set of spanning trees of \(G\) (respectively, spanning arbors of \(G\) rooted at a fixed vertex \(v_1\), given fixed roots \(v_i\in P_i\)) whose restriction to each part \(P_i\) is itself a spanning tree of \(G[P_i]\) (respectively, a spanning arbor of \(G[P_i]\) rooted at \(v_i\)).
We show (Theorem 3.6 for digraphs, Theorem 4.4 for graphs) that this generating function factors as a product of \(k+1\) determinants: one reduced-Laplacian determinant for each part \(P_i\), and one further reduced-Laplacian determinant for a contracted multigraph \(\Gamma_P\) whose \(k\) vertices are the parts of \(P\) and whose edges are the edges of \(G\) that run between distinct parts. Because \(\Gamma_P\) has fewer vertices and fewer edges than \(G\), this gives an inductive route to bounding and computing the number of spanning trees of \(G\); we develop this in Section 5, obtaining an exact partition identity (Theorem 5.2) and a family of lower bounds (Theorem 5.5) on \(t(G)\), the number of spanning trees of \(G\).
The results specialize, when \(P\) has singleton parts, to the theorems of Kirchhoff and Tutte, and when \(P\) has a single non-trivial part, to a fixed-forest/fixed-arborescence contraction result (Propositions 3.3 and 4.2) in the spirit of [3].
We work with labeled vertices and allow multiple edges throughout.
Convention 2.1. If \(G\) is a digraph and there is an edge from vertex \(i\) to vertex \(j\), we associate to it an indeterminate \(x_{ij}\); if there are several parallel edges from \(i\) to \(j\) we label them with distinct indeterminates \(x_{ij}^{(1)},x_{ij}^{(2)},\dots\), and write \(\sum\limits_{r}x_{ij}^{(r)}\) for their total. If \(G\) is undirected, a single edge \(\{i,j\}\) is associated with one indeterminate, written \(x_{ij}=x_{ji}\) (the same variable regardless of which endpoint is listed first); parallel undirected edges again receive distinct indeterminates. To a rooted arbor (or, in the undirected case, a tree) \(A\) with edges \(i_1j_1,i_2j_2,\dots\) we associate the monomial \(m(A)=x_{i_1j_1}x_{i_2j_2}\cdots\), and to a set \(S\) of such objects the generating function \(f(S)=\sum\limits_{A\in S}m(A)\).
Convention 2.2. The Laplacian \(L\) of a digraph \(G\) is the vertex-by-vertex matrix with \((i,j)\) entry, for \(i\neq j\), equal to \(-\sum\limits_r x_{ij}^{(r)}\) if edges from \(i\) to \(j\) exist and \(0\) otherwise, and with \(m\)th diagonal entry equal to the negative of the sum of the off-diagonal entries in row \(m\). For a vertex \(v\) of \(G\), \(L_v\) denotes \(L\) with the row and column indexed by \(v\) deleted.
Convention 2.3 (Contraction and loops). Whenever we contract a graph or digraph \(G\) along a partition \(P=\{P_1,\dots,P_k\}\) (or along a spanning forest/arborescence, the special case in which each \(P_i\) is itself required to already carry a fixed local tree structure), the resulting multigraph has vertex set \(\{P_1,\dots,P_k\}\) and, by definition, has as edges only those edges of \(G\) with endpoints in two different parts; edges of \(G\) with both endpoints in the same part are simply not part of the contraction. In particular no loops are ever created, and this does not need to be imposed separately. Edges retain their original labels \(x_{ij}^{(r)}\) from \(G\), so the contracted multigraph typically has parallel edges even when \(G\) does not.
Theorem 2.4 (Tutte). The generating function of the set of spanning arbors of a digraph \(G\) rooted at \(v\) is the formal expansion of \(\det L_v\).
Theorem 2.5 (Kirchhoff). The generating function of the set of spanning trees of a graph \(G\) is the formal expansion of \(\det L_v\); the result does not depend on the choice of \(v\).
Given a digraph (or graph) \(G\) and \(H\subseteq V(G)\), \(G[H]\) denotes the induced subgraph on \(H\): its vertex set is \(H\) and its edges are exactly the edges of \(G\) with both endpoints in \(H\). A partition of \(G\) is a partition \(P=\{P_1,\dots,P_k\}\) of \(V(G)\), each part identified with the induced subgraph \(G[P_i]\).
Let \(G\) be a digraph and fix a spanning arborescence \(A\) of \(G\) with arbors \(A_1,\dots,A_k\) rooted at \(v_1,\dots,v_k\). We first isolate, among all spanning arbors of \(G\) rooted at \(v_1\), those that contain \(A\); this is the case of Theorem 3.6 below in which the local tree structure on each part is already fixed.
Definition 3.1. Let \(\Gamma_A\) be the digraph with vertex set \(\{A_1,\dots,A_k\}\) and an edge \(A_i\to A_j\) for every edge of \(G\) that originates at a root \(v_i\), \(i>1\), and terminates at some vertex of \(A_j\), \(j\neq i\) (Convention 2.3); edges keep their original \(G\)-labels.
The restriction to edges originating at the roots \(v_i\), \(i>1\), is not an arbitrary choice of convenience; it is forced by the requirement that the result be a spanning arbor.
Lemma 3.2. Let \(T\) be a spanning arbor of \(G\) rooted at \(v_1\) that contains \(A\) as a sub-digraph. Then the edges of \(T\) not in \(A\) are exactly \(k-1\) edges, one originating at each root \(v_i\), \(i>1\), and each terminating at a vertex lying outside the arbor \(A_i\) that contains its tail.
Proof. In a spanning arbor rooted at \(v_1\), every vertex other than \(v_1\) has out-degree exactly \(1\), and \(v_1\) has out-degree \(0\). Inside \(A\), every vertex of \(A_i\) other than the root \(v_i\) already has out-degree \(1\) (its edge toward \(v_i\) within \(A_i\)), so it can receive no further outgoing edge in \(T\). The root \(v_1\) needs no outgoing edge. Each remaining root \(v_i\), \(i>1\), has out-degree \(0\) within \(A\) and so needs exactly one outgoing edge in \(T\setminus A\). This accounts for exactly \(k-1\) additional edges, one per root \(v_i\), \(i>1\). Such an edge cannot terminate inside \(A_i\) itself: every vertex of \(A_i\) already has a directed path, within \(A_i\), back to \(v_i\), so an edge from \(v_i\) into \(A_i\) would close a cycle. Hence each additional edge terminates at a vertex of some \(A_j\), \(j\neq i\). \(\square\)
Proposition 3.3. Let \(G\), \(A\), \(A_1,\dots,A_k\), \(v_1,\dots,v_k\), and \(\Gamma_A\) be as above. The generating function of the spanning arbors of \(G\) rooted at \(v_1\) that contain \(A\) is \[F^{v_1}_{G,A} \;=\; \Bigl(\prod_{ij\in A}x_{ij}\Bigr)\cdot \det L(\Gamma_A)_{A_1},\] where \(L(\Gamma_A)_{A_1}\) is the Laplacian of \(\Gamma_A\) with the row and column indexed by \(A_1\) deleted.
Proof. By Lemma 3.2, a spanning arbor \(T\) of \(G\) rooted at \(v_1\) containing \(A\) consists of the edges of \(A\) together with a choice, for each root \(v_i\), \(i>1\), of exactly one outgoing edge to a vertex outside \(A_i\), subject to the constraint that the resulting digraph is acyclic. Collapsing each arbor \(A_i\) to the single vertex it represents in \(\Gamma_A\), such a choice is precisely a spanning arbor \(\overline T\) of \(\Gamma_A\) rooted at \(A_1\): each vertex \(A_i\), \(i>1\), has exactly one outgoing edge, \(A_1\) has none, and acyclicity of \(T\) on the roots corresponds to acyclicity of \(\overline T\). Conversely, any spanning arbor \(\overline T\) of \(\Gamma_A\) rooted at \(A_1\) lifts uniquely to a spanning arbor \(T\supseteq A\) of \(G\) rooted at \(v_1\), since within each \(A_i\) all edges already point toward \(v_i\). The correspondence \(T\leftrightarrow\overline T\) is therefore a bijection between \(\{T : T \text{ a spanning arbor of } G \text{ rooted at } v_1,\ T\supseteq A\}\) and the spanning arbors of \(\Gamma_A\) rooted at \(A_1\), and \(m(T)=\bigl(\prod_{ij\in A}x_{ij}\bigr)\cdot m(\overline T)\). Summing over \(T\) and applying Tutte’s theorem (Theorem 2.4) to \(\Gamma_A\) gives the stated formula. \(\square\)
Setting all \(x_{ij}=1\) shows that the number of spanning arbors of \(G\) rooted at \(v_1\) containing \(A\) is \(\det L(\Gamma_A)_{A_1}\); and when every arbor \(A_i\) is a single vertex, \(\Gamma_A=G\) and Proposition 3.3 recovers Tutte’s theorem.
Example 3.4. Write \(i\) for vertex \(v_i\) and \(ij\) for the edge from \(v_i\) to \(v_j\). Let \(G\) be the digraph on six vertices with edges \(12,21,32,34,24,25,41,54,61,65\). Fix the arborescence \(A\) with arbors \(A_1=\{54,41\}\) rooted at \(1\), \(A_2=\{32\}\) rooted at \(2\), and \(A_3=\{6\}\) rooted at \(6\). Then \(\Gamma_A\) has vertex set \(\{A_1,A_2,A_3\}\) and edges \(21,25,24\) (from root \(2\)) and \(61,65\) (from root \(6\)). Proposition 3.3 gives \[\begin{aligned} F_{G,A}^{1} =& (x_{54}x_{41}x_{32})\cdot\det L(\Gamma_A)_{A_1}\\ =&(x_{54}x_{41}x_{32})\,(x_{21}x_{61}+x_{21}x_{65}+x_{25}x_{61}+x_{25}x_{65}+x_{24}x_{61}+x_{24}x_{65}), \end{aligned}\] a sum of six monomials, confirming by direct inspection that there are exactly six spanning arbors of \(G\) rooted at \(1\) that contain \(A\).
We now localize to an arbitrary partition, rather than a single fixed arborescence: instead of fixing the local arbors \(A_i\) in advance, we ask for the union, over all choices of a local arbor in each part, of the resulting spanning arbors of \(G\).
Definition 3.5. Let \(G\) be a digraph and \(P=\{P_1,\dots,P_k\}\) a partition of \(G\) with fixed vertices \(v_i\in P_i\). Write \(v=(v_1,\dots,v_k)\). Define \[\begin{aligned} S(P,v)=&\bigl\{\,T :{}\; T\text{ is a spanning arbor of }G\text{ rooted at }v_1,\text{and }T[P_i]\text{ is a spanning arbor of }\\ &\qquad P_i\;\text{rooted at }v_i\text{ for every }i \,\bigr\}. \end{aligned}\] where \(T[P_i]\) denotes the restriction of \(T\) to edges with both endpoints in \(P_i\). Let \(\Gamma_P\) be the digraph with vertex set \(\{P_1,\dots,P_k\}\) and an edge \(P_i\to P_j\) for every edge of \(G\) that originates at \(v_i\), \(i>1\), and terminates in \(P_j\), \(j\neq i\).
Theorem 3.6. With \(G\), \(P\), \(v\), and \(\Gamma_P\) as above, the generating function of \(S(P,v)\) is \[\Bigl(\prod_{i=1}^k \det L(P_i)_{v_i}\Bigr)\cdot \det L(\Gamma_P)_{P_1}.\]
Proof. Fix, for each \(i\), a spanning arbor \(A_i\) of \(P_i\) rooted at \(v_i\); let \(A=A_1\cup\cdots\cup A_k\), a spanning arborescence of \(G[P_1\cup\cdots\cup P_k]=G\) rooted at \(v_1,\dots,v_k\). By the argument of Lemma 3.2 and Proposition 3.3, applied verbatim with \(A_i\) in the role of the arbors of \(A\), the elements of \(S(P,v)\) that contain this particular choice of local arbors are in bijection with the spanning arbors of the digraph \(\Gamma_A\) (vertex set \(\{A_1,\dots,A_k\}\), edges from roots \(v_i\), \(i>1\), into other \(A_j\)) rooted at \(A_1\). Because these edges of \(\Gamma_A\) are determined only by which root \(v_i\) they originate at and which part \(P_j\) they terminate in — not by the internal structure of \(A_i\) or \(A_j\) — the digraph \(\Gamma_A\) is identical, as a labeled multigraph, to \(\Gamma_P\) for every choice of local arbors \(A_1,\dots,A_k\). Hence \[S(P,v)=\bigsqcup_{\substack{A_i\in\mathcal A(P_i,v_i)\\ i=1,\dots,k}} \{\,T : T\supseteq A_1\cup\cdots\cup A_k,\ T \text{ a spanning arbor of }G\text{ rooted at }v_1\,\},\] where \(\mathcal A(P_i,v_i)\) is the set of spanning arbors of \(P_i\) rooted at \(v_i\), and this union is disjoint because two spanning arbors \(T\) of \(G\) containing different tuples \((A_1,\dots,A_k)\) restrict to different arbors on some \(P_i\). By Proposition 3.3, the generating function of the \(A\)-indexed block is \(\bigl(\prod_i m(A_i)\bigr)\cdot\det L(\Gamma_P)_{P_1}\); the determinant is the same for every choice of \((A_1,\dots,A_k)\), since \(\Gamma_A=\Gamma_P\) regardless. Summing over all choices, \[\begin{aligned} f(S(P,v)) =& \Bigl(\sum\limits_{A_1\in\mathcal A(P_1,v_1)}m(A_1)\Bigr)\cdots \Bigl(\sum\limits_{A_k\in\mathcal A(P_k,v_k)}m(A_k)\Bigr)\cdot\det L(\Gamma_P)_{P_1}\\ =&\Bigl(\prod_{i=1}^k \det L(P_i)_{v_i}\Bigr)\cdot\det L(\Gamma_P)_{P_1}, \end{aligned}\] the last step by Tutte’s theorem applied to each \(P_i\). If some \(P_j\) has no spanning arbor rooted at \(v_j\), then \(\mathcal A(P_j,v_j)=\varnothing\), \(S(P,v)=\varnothing\), and \(\det L(P_j)_{v_j}=0\) by Theorem 2.4, so the formula still holds (both sides are \(0\)). \(\square\)
Example 3.7. Let \(G\) have edges \(21,32,31,34,45,53,51\). Take \(P=\{P_1,P_2\}\) with \(P_1=\{1,2,3\}\) (induced edges \(21,32,31\)) and \(P_2=\{4,5\}\) (induced edge \(45\)); root \(P_1\) at \(v_1=1\) and \(P_2\) at \(v_2=5\). Direct inspection shows the elements of \(S(P,v)\) have generating function \(x_{21}x_{31}x_{45}x_{51}+x_{21}x_{31}x_{45}x_{53}+x_{32}x_{21}x_{45}x_{51}+x_{32}x_{21}x_{45}x_{53}\). Theorem 3.6 gives, with \(\Gamma_P\) having the two edges \(53,51\) from root \(v_2=5\) into \(P_1\) (the third \(P_1\)–\(P_2\) edge, \(34\), does not originate at \(v_2\) and so is not an edge of \(\Gamma_P\)), \[\bigl(\det L(P_1)_1\cdot\det L(P_2)_5\bigr)\cdot \det L(\Gamma_P)_{P_1} = (x_{21}x_{31}+x_{32}x_{21})\cdot x_{45}\cdot(x_{51}+x_{53}),\] which agrees with the direct computation upon expanding.
Now instead take \(P_1=\{1,5\}\) with induced edge \(51\) only, and \(P_2=\{2,3,4\}\) with induced edges \(32,34\); root \(P_1\) at \(1\) and \(P_2\) at \(2\). Then \(P_2\) has no spanning arbor rooted at \(2\) (vertex \(4\) has no outgoing edge within \(P_2\)), so \(S(P,v)=\varnothing\), and indeed \(\det L(P_2)_2=0\).
We now treat the undirected analogue. Throughout this section all graphs are undirected; for an edge \(\{i,j\}\) we always have \(x_{ij}=x_{ji}\) (Convention 2.1), and we write \(ij\) for the unordered edge.
Definition 4.1. Let \(G\) be a graph and \(F\) a spanning forest of \(G\) with trees \(T_1,\dots,T_k\). Let \(G/F\) be the multigraph with vertex set \(\{T_1,\dots,T_k\}\) and, for \(i\neq j\), an edge between \(T_i\) and \(T_j\) for every edge of \(G\) joining a vertex of \(T_i\) to a vertex of \(T_j\) (Convention 2.3); edges keep their original labels.
Proposition 4.2. The generating function of the spanning trees of \(G\) that contain \(F\) is \[\sum\limits_{\substack{T \text{ spanning tree of }G\\ F\subseteq T}} m(T) \;=\; \Bigl(\prod_{ij\in F}x_{ij}\Bigr)\cdot\det L(G/F)_v,\] for any vertex \(v\) of \(G/F\) (the choice of \(v\) does not affect the value, by Theorem 2.5).
Proof. We exhibit mutually inverse maps between \(\{T : T \text{ a spanning tree of }G,\ F\subseteq T\}\) and the spanning trees of \(G/F\).
Forward map. Let \(T\supseteq F\) be a spanning tree of \(G\). The edge set \(T\setminus F\), viewed as edges of \(G/F\) between the corresponding trees \(T_i,T_j\), has \(|T|-|F|=(n-1)-(n-k)=k-1\) edges, where \(n=|V(G)|\). It contains no cycle: a cycle in \(G/F\) using edges of \(T\setminus F\) would lift, via paths inside the relevant \(T_i\)’s supplied by \(F\), to a cycle in \(T\), contradicting that \(T\) is a tree. A graph on \(k\) vertices with \(k-1\) edges and no cycle is connected, hence \(T\setminus F\) is a spanning tree \(\overline T\) of \(G/F\).
Backward map. Let \(\overline T\) be a spanning tree of \(G/F\), i.e. \(k-1\) edges of \(G\) running between distinct \(T_i\)’s, forming (as a graph on \(\{T_1,\dots,T_k\}\)) a tree. Set \(T=F\cup \overline T\), viewed as a set of edges of \(G\). Then \(T\) has \((n-k)+(k-1)=n-1\) edges and spans all \(n\) vertices; it is connected because \(F\) connects each \(T_i\) internally and \(\overline T\) connects the \(T_i\)’s to one another; and it is acyclic because a cycle would either lie inside some \(T_i\) (impossible, \(F\) restricted to \(T_i\) is a tree) or would have to cross between at least two parts using at least two edges of \(\overline T\) between the same pair of “super-vertices” in a way that closes a cycle in \(G/F\), contradicting that \(\overline T\) is a tree of \(G/F\). So \(T\) is a spanning tree of \(G\) containing \(F\).
These two maps are mutually inverse, giving a bijection \(T\leftrightarrow \overline T\) with \(m(T)=\bigl(\prod_{ij\in F}x_{ij}\bigr)\cdot m(\overline T)\). Summing over \(T\) and applying Kirchhoff’s theorem (Theorem 2.5) to \(G/F\) gives the stated identity. \(\square\)
Setting \(x_{ij}=1\) for all \(ij\), Proposition 4.2 says the number of spanning trees of \(G\) containing \(F\) is \(\det L(G/F)_v\); when \(F\) consists solely of vertices of \(G\) this recovers Kirchhoff’s theorem.
We next pass, exactly as in Section 3, from a single fixed forest \(F\) to a partition \(P\), taking the union over all choices of local spanning tree in each part.
Definition 4.3. Let \(G\) be a graph and \(P=\{P_1,\dots,P_k\}\) a partition of \(G\). Set \[S(P) = \bigl\{\,T : T \text{ a spanning tree of }G,\ T[P_i]\text{ a spanning tree of }G[P_i]\text{ for every }i\,\bigr\}.\] Let \(G_P\) be the multigraph with vertex set \(\{P_1,\dots,P_k\}\) and, for \(i\neq j\), an edge between \(P_i\) and \(P_j\) for every edge of \(G\) joining a vertex of \(P_i\) to a vertex of \(P_j\).
Theorem 4.4. With \(G\), \(P\), \(G_P\) as above, and \(u_i\) any vertex of \(P_i\), \(v\) any vertex of \(G_P\), the generating function of \(S(P)\) is \[\Bigl(\prod_{i=1}^k\det L(G[P_i])_{u_i}\Bigr)\cdot\det L(G_P)_v.\]
If some \(G[P_i]\) is disconnected, \(\det L(G[P_i])_{u_i}=0\) and \(S(P)=\varnothing\).
Proof. Exactly as in the proof of Theorem 3.6: fixing a spanning tree \(T_i\) of each \(G[P_i]\) gives a spanning forest \(F=T_1\cup\cdots\cup T_k\) of \(G\), and by Proposition 4.2 the spanning trees of \(G\) containing this \(F\) biject with the spanning trees of \(G/F\); the multigraph \(G/F\) depends only on the partition \(\{P_1,\dots,P_k\}\) induced by \(F\)’s components, not on the particular local trees \(T_i\) chosen, so \(G/F=G_P\) for every choice. Hence \(S(P)\) is the disjoint union, over all tuples \((T_1,\dots,T_k)\) with \(T_i\) a spanning tree of \(G[P_i]\), of the (bijective, by Proposition 4.2) fibers indexed by the spanning trees of \(G_P\), and \[f(S(P))=\Bigl(\sum\limits_{T_1}m(T_1)\Bigr)\cdots\Bigl(\sum\limits_{T_k}m(T_k)\Bigr)\cdot \det L(G_P)_v =\Bigl(\prod_{i=1}^k\det L(G[P_i])_{u_i}\Bigr)\cdot\det L(G_P)_v,\] using Kirchhoff’s theorem on each \(G[P_i]\); the choice of \(u_i\), \(v\) is immaterial by Theorem 2.5. If \(G[P_i]\) is disconnected for some \(i\), it has no spanning tree, \(\det L(G[P_i])_{u_i}=0\) by Kirchhoff’s theorem, and \(S(P)=\varnothing\) since no \(T\in S(P)\) can restrict to a spanning tree on a disconnected part. \(\square\)
Setting \(x_{ij}=1\) in Proposition 4.2 (not Theorem 4.4, which counts a different, larger set) gives the number of spanning trees of \(G\) containing a fixed forest \(F\) as \(\det L(G/F)_v\).
Example 4.5. We recover Cayley’s formula, and a refinement of it, from Proposition 4.2 applied to \(G=K_n\). Fix a spanning forest \(F\) of \(K_n\) with trees \(T_1,\dots,T_k\) on \(n_1,\dots,n_k\) vertices, \(\sum\limits_i n_i=n\). By Convention 2.3, \(K_n/F\) has vertices \(1,\dots,k\) (relabeling \(T_1,\dots,T_k\)) with exactly \(n_in_j\) parallel edges between vertices \(i\) and \(j\) (\(i\neq j\)), all edges of \(K_n\) between \(T_i\) and \(T_j\) being present. Its Laplacian \(L\) has off-diagonal entries \(L_{ij}=-n_in_j\) (\(i\neq j\)) and diagonal entries \[L_{ii}=\sum\limits_{j\neq i}n_in_j = n_i(n-n_i),\] by Convention 2.2. Writing \(\mathbf n=(n_1,\dots,n_k)^{\mathsf T}\) and \(D=\operatorname{diag}(n_1,\dots,n_k)\), this is \[L = nD – \mathbf n\mathbf n^{\mathsf T}.\]
Delete the row and column indexed by \(k\); write \(D’=\operatorname{diag}(n_1,\dots,n_{k-1})\) and \(\mathbf n’=(n_1,\dots,n_{k-1})^{\mathsf T}\), so \(L_k = nD’-\mathbf n’\mathbf {n’}^{\mathsf{T}}\). Since \(D’\) is invertible with \({D’}^{-1}\mathbf n’=(1,\dots,1)^{\mathsf{T}}=:\mathbf 1\), the matrix determinant lemma \(\det(A-uv^{\mathsf T})=\det(A)(1-v^{\mathsf T}A^{-1}u)\), applied with \(A=nD’\), \(u=v=\mathbf n’\), gives \[\begin{aligned} \det L_k =& \det(nD’)\Bigl(1-\tfrac1n\,{\mathbf n’}^{\mathsf T}{D’}^{-1}\mathbf n’\Bigr)\\ =& n^{k-1}\prod_{i=1}^{k-1}n_i \cdot\Bigl(1-\tfrac1n\sum\limits_{i=1}^{k-1}n_i\Bigr)\\ =& n^{k-1}\prod_{i=1}^{k-1}n_i\cdot\frac{n_k}{n}\\ =&n^{k-2}\prod_{i=1}^k n_i, \end{aligned}\] using \(\sum\limits_{i=1}^{k-1}n_i=n-n_k\). By Proposition 4.2 at \(x_{ij}\equiv1\), this is exactly the number of spanning trees of \(K_n\) containing the fixed forest \(F\): \[\#\{\text{spanning trees of }K_n\text{ containing }F\} = n^{k-2}\prod_{i=1}^k n_i,\] depending only on the component sizes \(n_1,\dots,n_k\), not on the isomorphism type of the \(T_i\) or on which forest with these component sizes was chosen. Taking \(k=n\) (all \(n_i=1\), \(F=\varnothing\)) recovers Cayley’s theorem, \(t(K_n)=n^{n-2}\) [4]. Combining with Theorem 4.4 and Cayley’s formula applied inside each block (\(t(K_{n_i})=n_i^{n_i-2}\)) also gives the number of spanning trees of \(K_n\) whose restriction to a fixed partition into blocks of sizes \(n_1,\dots,n_k\) is connected (any local tree allowed): \(n^{k-2}\prod_i n_i \cdot \prod_i n_i^{n_i-2}=n^{k-2}\prod_i n_i^{n_i-1}\). See [3] for related enumeration.
Remark 4.6. It would be of interest to extend Theorems 3.6 and 4.4 to graphs and digraphs with colored edges, along the lines of [2, 1].
We now use the results of Section 4 to relate \(t(G)\), the number of spanning trees of \(G\) (\(n=|V(G)|\) vertices), to spanning-tree counts of smaller induced subgraphs. For a spanning forest \(f\) of \(G\), write \(t(G/f)\) for the number of spanning trees of \(G\) containing \(f\); by Proposition 4.2 at \(x_{ij}\equiv1\), \(t(G/f)=\det L(G/f)_v\).
Theorem 5.1. For any \(1\le k\le n\), \[t(G) = \binom{n-1}{n-k}^{-1}\sum\limits_{f} t(G/f),\] the sum over all spanning forests \(f\) of \(G\) with exactly \(k\) trees (isolated vertices count as one-vertex trees).
Proof. Count pairs \[\mathcal T=\{(f,t): f \text{ a spanning forest of }G\text{ with }k\text{ trees},\ f\subseteq t, t\text{ a spanning tree of }G\}\] in two ways. Fixing a spanning tree \(t\) (which has \(n-1\) edges), the forests \(f\subseteq t\) with \(k\) trees are obtained by deleting exactly \(n-k\) of its \(n-1\) edges, in \(\binom{n-1}{n-k}\) ways; so \(|\mathcal T|=\binom{n-1}{n-k}t(G)\). Fixing \(f\) instead, the number of \(t\) with \(f\subseteq t\) is \(t(G/f)\) by definition; so \(|\mathcal T|=\sum\limits_f t(G/f)\). Equating the two counts and dividing gives the formula. \(\square\)
Because \(G/f\) depends only on the partition of \(V(G)\) into the vertex sets of \(f\)’s components (not on the internal edges of \(f\)), and because the number of spanning forests \(f\) inducing a given partition \(p=\{V_1,\dots,V_k\}\) of \(V(G)\) (each \(V_i\) connected) is \(\prod_i t(G[V_i])\), Theorem 5.1 may be rewritten as a sum over set partitions rather than over forests.
Theorem 5.2 (Exact partition identity). For any \(1\le k\le n\), \[t(G) = \binom{n-1}{n-k}^{-1}\sum\limits_{p}\Bigl(\prod_{i=1}^k t(G[V_{i,p}])\Bigr)\,t(G_p),\] the sum over all partitions \(p=\{V_{1,p},\dots,V_{k,p}\}\) of \(V(G)\) into \(k\) (labeled or unlabeled – the summand is symmetric) blocks, where \(G_p\) is the contracted multigraph of Theorem 4.4 and \(t(G[V_{i,p}])=0\) whenever \(V_{i,p}\) does not induce a connected subgraph.
Proof. Group the sum in Theorem 5.1 by the partition \(p\) that a forest \(f\) induces: for fixed \(p\) with each block connected, the forests \(f\) inducing \(p\) are exactly the \(\prod_it(G[V_{i,p}])\) choices of a spanning tree in each block, and for every such \(f\), \(G/f=G_p\) (Convention 2.3: the contraction depends only on the blocks, not on which spanning tree was chosen within them), so \(t(G/f)=t(G_p)\) for all of them. Summing \(t(G/f)=t(G_p)\) over the \(\prod_i t(G[V_{i,p}])\) forests inducing \(p\), and then over all \(p\) (partitions with a disconnected block contribute \(0\), matching that no forest with \(k\) components induces them), reproduces \(\sum\limits_f t(G/f)\). \(\square\)
Corollary 5.3 (\(k=2\)). \[t(G) = \frac{1}{n-1}\sum\limits_{p} t(G[V_{1,p}])\,t(G[V_{2,p}])\,e_p,\] the sum over the (unordered) partitions \(p=\{V_{1,p},V_{2,p}\}\) of \(V(G)\) into two blocks, where \(t(G[V_{i,p}]) :=\) the number of spanning trees of the induced subgraph \(G[V_{i,p}]\), and \(e_p:=\bigl|\{uv\in E(G): u\in V_{1,p},\ v\in V_{2,p}\}\bigr|\).
Proof. Immediate from Theorem 5.2 at \(k=2\): the two-vertex multigraph \(G_p\) has \(t(G_p)=e_p\), since any single one of its \(e_p\) parallel edges is by itself a spanning tree. \(\square\)
Example 5.4. Let \(G\) have vertices \(1,2,3,4\) and all edges present except \(24\). There are \(10\) partitions of \(\{1,2,3,4\}\) into two blocks. Of these, four have \(3\) edges of \(G\) running between the blocks and six have \(2\) edges between the blocks, and in every one of these ten partitions both blocks induce connected subgraphs with a single spanning tree each; direct enumeration gives \(\sum\limits_p t(G[V_{1,p}])t(G[V_{2,p}])e_p = 4\cdot3+6\cdot2=24\). By Corollary 5.3, \(t(G)=\tfrac1{3}\cdot24=8\), which agrees with direct enumeration of the spanning trees of \(G\).
For general \(k\), Theorem 5.2 sums nonnegative terms over all partitions with \(k\) blocks; restricting the sum to a subset of these partitions can only decrease it, and every term already vanishes unless every block is connected. This gives a lower bound, correcting the direction claimed in an earlier draft of this result.
Theorem 5.5 (Lower bound). Let \(\mathcal Q\) be any set of partitions of \(V(G)\) into \(k\) blocks. Then \[\binom{n-1}{n-k}^{-1}\sum\limits_{p\in\mathcal Q}\Bigl(\prod_{i=1}^k t(G[V_{i,p}])\Bigr)t(G_p)\ \le\ t(G),\] with equality if and only if \(\mathcal Q\) contains every partition of \(V(G)\) into \(k\) blocks all of which induce connected subgraphs of \(G\) (partitions with a disconnected block may freely be included or omitted, as they contribute \(0\) either way).
Proof. By Theorem 5.2, \(\binom{n-1}{n-k}\,t(G)=\sum\limits_{p}\bigl(\prod_i t(G[V_{i,p}])\bigr)t(G_p)\), the sum over all partitions \(p\) into \(k\) blocks, with every summand nonnegative. Restricting the sum to \(p\in\mathcal Q\subseteq\{\text{all partitions into }k\text{ blocks}\}\) removes only nonnegative terms, so \(\sum\limits_{p\in\mathcal Q}(\cdots)\le \binom{n-1}{n-k}t(G)\); dividing gives the stated inequality. Equality holds exactly when the omitted terms are all \(0\), i.e. when every partition not in \(\mathcal Q\) has some disconnected block. \(\square\)
Remark 5.6. Theorem 5.5 is most useful when \(\mathcal Q\) is a small, structured family of partitions – for instance, all partitions obtained by removing a fixed small edge cut, or all partitions into \(k\) blocks of prescribed sizes – for which the local factors \(t(G[V_{i,p}])\) and the contracted count \(t(G_p)\) can be computed or bounded on graphs substantially smaller than \(G\).
We have shown that the generating function of the spanning trees of a graph \(G\) (or spanning arbors of a digraph, rooted appropriately) that respect a given vertex partition \(P\) – restricting to a spanning tree, or arbor, on each part – factors as the product of the local generating functions on the parts and the generating function of a naturally associated contracted multigraph on the parts. This localizes Kirchhoff’s and Tutte’s theorems (Theorems 3.6 and 4.4), specializes to a fixed-forest contraction result (Propositions 3.3 and 4.2) that recovers and refines Cayley’s formula on \(K_n\) (Example 4.5), and yields both an exact identity (Theorem 5.2) and a family of lower bounds (Theorem 5.5) for \(t(G)\) in terms of spanning-tree counts of induced subgraphs on fewer vertices.
Natural directions for further work include: an analogous treatment of edge-colored graphs and digraphs, in which the generating function tracks color multiplicities ([2, 1]); explicit families of partitions \(\mathcal Q\) in Theorem 5.5 for which the lower bound can be shown to be tight or near-tight; and a corresponding upper-bound theory, which does not follow from the present argument and appears to require different techniques.
This work was supported by grant number 2424684 from the National Science Foundation of the United States.