WorksMathematics
Upper bounds for the number of spanning forests of a graph
Abstract
Let be a simple graph on vertices, and let denote the number of spanning forests of . Bencs and Csikvári proved that every -regular graph with satisfies . Motivated by this result, they conjectured that if has minimum degree at least , then , where is the degree sequence of . In this paper, we prove that graphs with minimum degree at least satisfy . We also construct a counterexample to the conjecture. We therefore further study the enumeration of spanning forests in general graphs, proving an upper bound in terms of the degree sequence and characterizing the extremal graphs attaining this bound. In addition, using the matrix-forest theorem, we obtain an upper bound for the number of spanning forests of a connected graph in terms of its algebraic connectivity, and characterize the extremal graphs attaining this bound.
Introduction
Throughout this paper, we consider only finite, simple, undirected graphs. Let be a graph with vertex set and edge set . The numbers of vertices and edges are denoted by and , respectively. If the number of edges of is , then is called an edgeless graph. For a vertex , let be its degree, that is, the number of edges incident with it. For , let denote the set of all vertices in adjacent to . Arranging all vertex degrees in nonincreasing order gives the degree sequence of , , where . If , then is called an -regular graph. If , then is called the complete graph of order , denoted by . Let denote the minimum degree of . If can be partitioned into two nonempty disjoint sets and , and the edges of the graph are precisely all possible edges joining vertices in these two sets, then is called a complete bipartite graph. When and , it is denoted by . The graph () is a star, whose vertex of degree is its center. When , either endpoint can serve as the center. The double star is obtained from two stars () and () by joining their centers with an edge. Let denote the connected graph with vertices and edges, obtained from the stars and by joining their centers and pairwise identifying leaves of with leaves of , where and .
For any subset , retain all vertices in and all edges of both of whose endpoints belong to . The resulting subgraph is called the subgraph induced by and is denoted by . When , we adopt the convention that is the graph with 0 vertices. Deleting from the vertices in and all edges incident with these vertices yields the graph denoted by ; that is, . In particular, when , we abbreviate as . For any notation not defined here, we refer the reader to [8].
A spanning forest of is a subgraph with that is acyclic; that is, it is obtained by retaining all vertices of and choosing an edge set such that is acyclic. The set of all spanning forests of and its cardinality are denoted, respectively, by
Determining the number of spanning forests of a graph is a classical problem in combinatorial enumeration; see [1, 2, 3, 6, 9, 13, 14, 17, 18, 19, 20]. Jaeger et al. [11] proved that computing is #P-hard. In 2021, Borbényi et al. established the following upper bound for the number of spanning forests.
Theorem 1.1. ([5]) Let be a graph on vertices. Then
For regular graphs, Bencs and Csikvári studied the number of spanning forests in 2023 and obtained the following upper bound.
Theorem 1.2. ([4]) Let be a graph on vertices that is -regular (). Then
Based on the two theorems above, they proposed the following conjecture.
Conjecture 1.1. Let be a graph on vertices. If , then
We investigate this conjecture and identify a class of graphs for which it holds.
Theorem 1.3. Let be a graph on vertices. If , then .
We also find a class of graphs that do not satisfy Conjecture 1.1. Let () be a complete bipartite graph whose vertex set is partitioned into and . We now construct a class of spanning forests of . For each vertex in , independently choose either to remain isolated or to be joined to one vertex in . Each such vertex has choices, and the resulting spanning subgraph is necessarily a spanning forest. Hence , and thus
Let be a fixed constant with . Since, as , we have , it follows that, as ,
Therefore, for every fixed constant , all sufficiently large integers satisfy
As a concrete example, consider . Applying Stark’s exact enumeration formula for spanning forests of complete bipartite graphs [16], we obtain
In view of these results, determining a sharp upper bound for the number of spanning forests of a general graph in terms of its degree sequence is an interesting problem. We investigate this problem and obtain the following theorem.
Theorem 1.4. Let be a graph on vertices. For , define and , where , and gives . Then
with equality if and only if is isomorphic to an edgeless graph, a star (), a double star , a graph , or the disjoint union of one of these graphs with isolated vertices.
Chebotarev and Shamis studied the number of spanning forests of a graph using its Laplacian spectrum and obtained the following upper bound.
Theorem 1.5. ([7]) Let be a graph on vertices, and let be its Laplacian matrix, with eigenvalues . Let denote the identity matrix of order . Then
with equality if and only if is an edgeless graph.
Using Theorem 1.5, we further characterize the relationship between the number of spanning forests of a connected graph and its algebraic connectivity, obtaining the following theorem.
Theorem 1.6. Let be a connected graph on vertices with algebraic connectivity and spanning trees. Then
with equality if and only if or .
The remainder of this paper is organized as follows. In § 2, we prove Theorem 1.6. In § 3, we prove Theorem 1.3. In § 4, we prove Theorem 1.4. Finally, we further discuss the comparison between the upper bounds in Theorem 1.4 and Theorem 1.6 for connected graphs.
Proof of Theorem 1.6
To prove Theorem 1.6, we first introduce a lemma.
Lemma 2.1. ([12]) Let be a graph on vertices, and let be its Laplacian matrix. For , write
Let
then
where denotes the set of all tree components of the forest . In particular, .
We now prove Theorem 1.6.
Proof of Theorem 1.6: For a graph on vertices, denoted by , let be a spanning forest of with edges, where . Thus, . Let the orders of its tree components be , and let . Since the number of edges in each tree component is , we have . Therefore,
If at least two of the are positive, then the corresponding quadratic term in the expansion of the product is positive, and the inequality in (4) is strict. Conversely, if at most one of the is positive, then all terms of degree at least 2 are 0. Thus, equality holds in (4) if and only if $\varphi has at most one tree component containing an edge. By Lemma 2.1, for every , we have
The Laplacian matrix is real symmetric and positive semidefinite, and , where denotes the vector whose entries are all . Therefore,
Combining (3) and (5) and integrating the preceding identity term by term yields
Equality holds in (6) if and only if every spanning forest of , denoted by , attains equality in (4), that is, has at most one component containing an edge, which is equivalent to the matching number of being at most one.
We now consider a connected graph on vertices, denoted by . By Lemma 2.1, we have . For , we have . Combining this with (6) gives
This proves (2).
We now discuss the equality case in (2), which is equivalent to equality holding simultaneously in (7) and (8). First, consider equality in (8). Then , so , where is the all-ones matrix. Since the off-diagonal entries of the Laplacian matrix can only be or , we obtain , that is, . Equality in (7) is equivalent to equality in (6), that is, the maximum matching of has at most edge. Thus, equality holds in (2) if and only if or . This completes the proof.
Proof of Theorem 1.3
To prove Theorem 1.3, we first introduce some lemmas.
Lemma 3.1. ([10]) Let be a real symmetric positive definite matrix of order , with the following block form:
where is a real number, is an column vector, and is a matrix of order . Then
Equality in the first inequality holds if and only if ; equality in the second inequality holds if and only if is a positive real multiple of the identity matrix.
Lemma 3.2. Let be a graph on vertices with no isolated vertices. Define
Then
Equality in (10) holds if and only if or .
Proof. Let denote the degree matrix of , abbreviated as . Define
Since is positive semidefinite and is positive definite, for every real number , the matrix is positive definite. Since , we have
Since , taking determinants on both sides of (11) gives
Let be an column vector. Since
is a unit vector. Since
we have . Let . Then
Let . Choose an real matrix whose columns form an orthonormal basis of . Then is an orthogonal matrix. Hence
Since is positive definite and the columns of are linearly independent, is also positive definite. Write . Then
Orthogonal similarity transformations preserve the trace of a matrix. Combining this with , we obtain
Since is also positive definite, . By Lemma 3.1, we have
Combining this with (12), we obtain, for every real number ,
which proves (10).
Equality in (10) holds if and only if equality holds in both (14) and (15). We first consider the case of equality in (15). In this case,
By (13), the function in square brackets above is continuous and nonnegative on . Hence, for every real number , we have
For (16) to hold, both equality conditions in (9) must be satisfied, namely, and is a positive real multiple of the identity matrix. From , it follows that is parallel to . Since has no isolated vertices and every coordinate of is nonzero, all are equal. Let ; that is, is -regular. Taking , since is a positive real multiple of the identity matrix and , we obtain
Since every off-diagonal entry of the Laplacian matrix is either or , we have , that is, . Equality in (14) holds if and only if equality holds in (6). Therefore, equality in (10) holds if and only if or . This completes the proof.
We now prove Theorem 1.3.
Proof of Theorem 1.3: Let be a graph on vertices with . For a real number , define
For every , we have . Combining with the preceding relation, we obtain
The function is strictly increasing for , whereas and is strictly decreasing for . Therefore,
is strictly decreasing for . Since is also strictly decreasing for , is strictly decreasing for . Substituting (18) into (10) gives
Since and (), we have
By the above discussion, either or guarantees that Conjecture 1.1 holds.
We first consider the case . Since , we have
Let . For , we have , and , so, for , Conjecture 1.1 holds.
When , the integrality of the degrees gives . Direct substitution into (17) gives (with the results rounded to two decimal places) , , , , . Thus, for all , we have , completing the proof of Theorem 1.3.
Proof of Theorem 1.4
To prove Theorem 1.4, we first introduce some definitions, notation, and lemmas.
A graph is called a pseudo-forest if each of its connected components is a tree or a unicyclic graph. For a graph , let denote the set of its spanning pseudo-forests, let denote the number of unicyclic components of a pseudo-forest , and let denote the set of its tree components. Let be a subset of . If no two edges in are adjacent in , then is called a matching of . Let denote the number of edges in , and let denote the set of all vertices covered by the matching . Let denote the set of all matchings of (including the empty matching).
Lemma 4.1. Let be a graph on vertices. For each vertex , let denote the degree of . Let be the weight of , and let . Define
where is the parameter vector, that is, . Then
When , both sides are taken to be 1.
Proof: Let . Then . In (19), expand the term corresponding to a matching as follows: each matching edge produces arrows and ; mark this pair of arrows and assign it weight . In the graph , for the matching , each uncovered vertex has two choices: either choose a neighbor and draw an arrow , with weight , or choose no neighbor and draw no arrow, with weight . The sum of the weights of all marked configurations obtained in this way is . Denote the new graph obtained from by the above procedure by . A vertex of with no outgoing arrow is called a root of . In the graph , let the total number of pairs of opposite arrows be .
Fix a graph . Each pair of opposite arrows can arise in two ways: either it is produced by a matching edge ; or, for the matching , two uncovered vertices and choose each other as neighbors and draw arrows and , respectively. Since each vertex has at most one outgoing arrow, these pairs of opposite arrows are pairwise vertex-disjoint. Hence each pair can be chosen independently to arise from the matching or not. Let be the set of indices of the arrow pairs marked as belonging to the matching. Then the weight of the part marked as belonging to the matching is . Summing over all choices of markings gives
Each marking corresponds uniquely, in the graph , to a term for the original matching in the expansion in (19). Therefore,
Here we no longer distinguish whether the pairs of opposite arrows in arise from matching edges, and denotes the set of all roots of .
Now retain only the edges of carrying arrows (deleting all edges without arrows), and then remove all arrows. In the spanning subgraph of obtained by this procedure, the number of edges in each connected component is at most the number of outgoing arrows, so . Thus this spanning subgraph is a pseudo-forest. Fix a pseudo-forest. We now sum all contributions on its connected components.
If a connected component is a tree , let be its number of vertices, its number of roots, and its number of pairs of opposite arrows. Counting the total number of outgoing arrows in two ways gives and , respectively. Hence . Thus can only be 1 or 0: when , we have . After choosing the unique root arbitrarily, all other edges must point toward this root along the unique paths in the tree, giving a total weight of ; when , we have . After choosing the unique edge carrying opposite arrows arbitrarily, all other arrows must point toward this edge. Each choice has weight , giving a total weight of . Therefore, the total contribution of a tree component is
If a connected component is unicyclic, let be its number of roots and its number of pairs of opposite arrows. The same arrow count gives , so . Its unique cycle must be oriented consistently, and all arrows outside the cycle must point toward it. Since the cycle has two possible orientations, the total contribution is 2.
Since the choices for different components are independent, combining (21) with a sum over all spanning pseudo-forests and taking the product of the contributions of their components gives (20), completing the proof. □
Remark 4.1. When all vanish, Lemma 4.1 reduces to the pseudo-forest expansion of the polynomial at given by Bencs and Csikvári [3, 4].
To illustrate Lemma 4.1, consider the graph (defined in the introduction), which is a triangle with one pendant edge, and set for every vertex. All 16 spanning subgraphs of are pseudo-forests. Each of the two spanning subgraphs containing all three edges of the triangle has exactly one unicyclic component, while the remaining 14 are forests. Thus, Eq. (20) yields . In Eq. (19), the empty matching contributes 72, the four single-edge matchings together contribute , and the unique two-edge matching contributes 4, yielding the same value.
Lemma 4.2. Let be a graph on vertices, and let be the graph obtained from by deleting
a vertex (). For each , let . For a vertex set , define
where , , and inherits the weights from . Then
Equality in (22) holds if and only if is a forest.
Proof: For , fix a spanning forest . We now add the vertex back to obtain spanning forests of . In , fix a tree component , and let the number of its vertices adjacent to be
There are two types of extensions for this tree component: the first is not to connect it to , for which there is only 1 possibility; the second is to connect one vertex of to , for which there are possibilities. If has 2 or more vertices connected to , a cycle is formed, contrary to the definition of a spanning forest. The two choices are mutually exclusive, so there are choices in total. Thus, for the fixed , the number of spanning forests of obtained is
For any spanning forest of , deleting the vertex and its incident edges uniquely determines a spanning forest of , denoted by . Conversely, given and the choices above for each of its tree components, a spanning forest of is uniquely determined. Hence there is a bijection between the spanning forests of and all together with the above choices. Summing over gives
The above analysis shows that, for each ,
Applying Lemma 4.1 gives , and hence . Thus the sum in (22) consists of exactly all the forest terms in (20). Therefore, , with equality in (22) if and only if is a forest.
For any vertex set and , let . By Lemma 4.1, both and are greater than 0, so . We divide the matchings of into two classes according to whether they cover the vertex , and use (19) to derive a recurrence for . First, consider matchings that do not cover the vertex . In this case, contributes a weight of to the weighted sum over matchings. The matching on the remaining vertices can be any matching of . Thus the total contribution of this class of matchings is . Next, consider matchings that cover the vertex . In this case, exactly one matching edge is incident with . Let this edge be ; it contributes a weight of . Since both and are covered by this matching edge, the remaining matching edges can only be chosen from the graph . Therefore, for a fixed , the total contribution of these matchings is . For , summing over all its neighbors gives
Combining the two cases above, we obtain
Dividing both sides of (25) by gives (23). In , take the vertex , apply (23), and take reciprocals to obtain
Substituting this into (23) gives . For the vertex and any of its neighbors in the sum, since , we have . Hence
This completes the proof.
We now prove Theorem 1.4.
Proof of Theorem 1.4: When , is edgeless, , and the right-hand side of (1) is also 1. Thus Theorem 1.4 clearly holds. Henceforth, assume .
For , let , , . Let . In Lemma 4.2, take and . We retain its notation and , with always equal to . By (22), we obtain
Write
By (24), we have
The neighbors of among number at most . Hence
Since , we have
If , arrange the elements of in increasing order as . Then , so
When , the corresponding . Hence, for every , we have
Therefore, for every , we have
All factors in (26), (27), and (30) are positive, so the inequalities can be multiplied term by term to give
This proves (1). We now discuss the case of equality in Theorem 1.4.
First, we prove necessity. Suppose that equality holds in (1) and that is not edgeless. Then . By (26), (27), and (30), for every , we have
Equality in (29) requires . Thus, when , we have . When , term-by-term comparison gives
On the other hand, (23) gives
Thus, for every , we have . For , applying (23) again gives
Since , we have . We consider two cases for : if , then for all , we have ; if , then , and for each , the corresponding vertex is isolated in , so its neighbors can only belong to , and hence . In (31), taking and , and using the equality conditions in (23), (27), and (28), we obtain (where is the smallest index in ). Thus, for all , we have
Hence is edgeless. Among the vertices of , let denote the numbers of vertices adjacent only to , only to , and to both , respectively. All remaining vertices are isolated. If , the graph obtained after deleting the isolated vertices is precisely . If and , the resulting graph is the double star . If and at least one of is 0, the resulting graph is the star . This proves necessity.
Next, we prove sufficiency. If is edgeless, then , and every factor on the right-hand side of (1) is 1, so equality holds.
For the star , the number of spanning forests is . Since and , we have , that is,
For the double star , the number of spanning forests is . Since
we have , that is,
Without loss of generality, assume that . Upon deleting the pendant vertices, the graph reduces to , namely the book graph consisting of triangles sharing a common edge. By [15],
Since every pendant edge is a bridge and hence lies on no cycle, the choice of including or omitting each pendant edge is independent of the choices made for the remaining pendant edges. Consequently,
Since
we have
that is,
Adding isolated vertices does not change the value of either side of (1). Hence all the graph classes above attain equality, proving sufficiency.
Further discussion
Sections 2 and 4 give two different upper bounds and their corresponding extremal graphs, respectively. A natural question arises: for which families of connected graphs with vertices and edges is one of the bounds smaller than the other?
For convenience of comparison, for any connected graph with vertices and edges, denoted by , write
We use several graph classes below to show that neither of these two upper bounds is uniformly better than the other.
For , the star has algebraic connectivity , and hence
For the double star and, when , the graph , equality holds in Theorem 1.4, but not in Theorem 1.6, and therefore
For , a calculation for the complete bipartite graph gives
For , we have , and applying this to the expression above gives
Thus,
The Laplacian eigenvalues of the complete bipartite graph are
so its algebraic connectivity is . From , we obtain , and therefore
Moreover, since
we have
Thus, for this family of complete bipartite graphs, the upper bound given by Theorem 1.6 is strictly better than that given by Theorem 1.4.
The above discussion shows that neither upper bound is uniformly tighter than the other. Consequently, a complete characterization of graph classes in terms of the relative sizes of these two upper bounds remains an open problem.
Conflict of Interest Statement
The authors declare that they have no conflicts of interest.
References
- [1]D. Aldous, R. Lyons, Processes on unimodular random networks, Electron. J. Probab. 12 (2007) 1454–1508.arxiv.org/abs/math/0603062
- [2]J.D. Annan, A randomised approximation algorithm for counting the number of forests in dense graphs, Combin. Probab. Comput. 3 (1994) 273–283.DOI
- [3]F. Bencs, P. Csikvári, Evaluations of Tutte polynomials of regular graphs, J. Combin. Theory Ser. B 157 (2022) 500–523.arxiv.org/abs/2105.06798
- [4]F. Bencs, P. Csikvári, Upper bound for the number of spanning forests of regular graphs, European J. Combin. 110 (2023) 103677.arxiv.org/abs/2105.06801
- [5]M. Borbényi, P. Csikvári, H. Luo, On the number of forests and connected spanning subgraphs, Graphs Combin. 37 (2021) 2655–2678.arxiv.org/abs/2005.12752
- [6]S. Caracciolo, J.L. Jacobsen, H. Saleur, A.D. Sokal, A. Sportiello, Fermionic field theory for trees and forests, Phys. Rev. Lett. 93 (2004) 080601.DOI
- [7]P. Chebotarev, E.V. Shamis, The matrix-forest theorem and measuring relations in small social groups, Autom. Remote Control 58 (1997) 1505–1514.
- [8]R. Diestel, Graph theory, fifth ed. , in: Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017, p. xviii+428.
- [9]G.R. Grimmett, S.N. Winkler, Negative association in uniform forests and connected graphs, Random Struct. Algorithms 24 (2004) 444–460.DOI
- [10]R.A. Horn, C.R. Johnson, Matrix Analysis, second ed., Cambridge University Press, Cambridge, 2013.
- [11]F. Jaeger, D.L. Vertigan, D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials, Math. Proc. Cambridge Philos. Soc. 108 (1990) 35–53.DOI
- [12]A.K. Kelmans, V.M. Chelnokov, A certain polynomial of a graph and graphs with an extremal number of trees, J. Combin. Theory Ser. B 16 (1974) 197–214.DOI
- [13]C.J. Liu, Y. Chow, Enumeration of forests in a graph, Proc. Amer. Math. Soc. 83 (1981) 659–662.DOI
- [14]J. Luo, T. Wu, Y.-N. Yeh, Counting spanning trees of multipartite graphs and those containing a fixed spanning forest, Discrete Appl. Math. 395 (2026) 317–336.DOI
- [15]S. Shteiner, P. Shteyner, Comparing the numbers of subforests and subgraph-degree-tuples, arXiv:2510.26936v1 (2025).arxiv.org/abs/2510.26936
- [16]D. Stark, The asymptotic number of spanning forests of complete bipartite labelled graphs, Discrete Math. 313 (2013) 1256–1261.DOI
- [17]Y. Teranishi, The number of spanning forests of a graph, Discrete Math. 290 (2005) 259–267.DOI
- [18]C. Thomassen, Spanning trees and orientations of graphs, J. Comb. 1 (2010) 101–111.DOI
- [19]T. Wu, S. Lu, X. Dong, A sharp upper bound on the number of spanning forests of regular graphs, preprint, arXiv:2610.05722v1 (2026).arxiv.org/abs/2610.05722
- [20]S. Xu, K. Xu, On asymptotic values for the minimum number of spanning forests in simple regular graphs, preprint, arXiv:2605.19707v2 (2026).arxiv.org/abs/2605.19707