pith. sign in

arxiv: 2605.19707 · v2 · pith:4MNJOTK7new · submitted 2026-05-19 · 🧮 math.CO

On asymptotic values for the minimum number of spanning forests in simple regular graphs

Shaohan Xu , Kexiang Xu This is my paper

Pith reviewed 2026-05-22 09:49 UTC · model grok-4.3

classification 🧮 math.CO
keywords spanning forestsregular graphsasymptotic enumerationliminfconnected graphsdegree sequencessimple graphsgraph enumeration
0
0 comments X

The pith

The exact asymptotic values of the minimum number of spanning forests are determined for large connected 3-regular and 4-regular graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper provides explicit lower bounds on the number of spanning forests F(G) expressed in terms of the counts n_i of vertices of each degree i, first for connected graphs whose degrees lie only in {2,3} and then for those whose degrees lie in {2,3,4}. These bounds are applied to sequences of d-regular graphs to compute the precise value of the liminf as n tends to infinity of F(G) raised to the power 1/n. A reader would care because the result fixes the slowest possible exponential growth rate of spanning-forest counts in arbitrarily large regular graphs of the two degrees, settling an extremal enumeration question for those families.

Core claim

Using lower bounds on F(G) written in terms of the n_i for graphs with vertex degrees restricted to {2,3} and to {2,3,4}, the authors prove that the liminf over all connected d-regular simple graphs of F(G)^{1/n} equals exact constants for d=3 and for d=4.

What carries the argument

Lower-bound expressions for the number of spanning forests written directly in terms of the numbers n_i of vertices of each allowed degree.

If this is right

  • The slowest exponential growth rate per vertex of spanning forests is now known exactly for all sufficiently large connected 3-regular graphs.
  • The same holds for all sufficiently large connected 4-regular graphs.
  • Any connected graph whose degrees lie in {2,3} obeys the stated lower bound on F(G) regardless of regularity.
  • Any connected graph whose degrees lie in {2,3,4} obeys its corresponding lower bound on F(G).

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same bounding technique may produce exact liminf values for regular graphs of higher fixed degree once suitable degree-set bounds are derived.
  • The results give a concrete benchmark against which numerical counts of spanning forests in large random regular graphs can be compared.
  • Because the bounds depend only on the n_i, they apply equally to non-regular graphs that are close to regular in degree distribution.

Load-bearing premise

The lower bounds derived for graphs with the restricted degree sets continue to hold for every connected graph in those classes, and the liminf is attained by some sequence of connected d-regular graphs whose order tends to infinity.

What would settle it

Exhibit an infinite family of connected 3-regular simple graphs whose number of spanning forests satisfies F(G)^{1/n} tending to a limit strictly smaller than the value claimed for hat f_3.

Figures

Figures reproduced from arXiv: 2605.19707 by Kexiang Xu, Shaohan Xu.

Figure 1
Figure 1. Figure 1: Graphs Hi and Zj for i ∈ [8] and j ∈ [3]. Remark 4.1. Theorem 1.2 is true for all graphs except K5 and K− 6 in [PITH_FULL_IMAGE:figures/full_fig_p012_1.png] view at source ↗
Figure 1
Figure 1. Figure 1: Graphs Hi and Zj for i ∈ [8] and j ∈ [3]. G F(G) q(G) F(G) ≥ q(G)? G F(G) q(G) F(G) ≥ q(G)? K3 7 2 6 5 198 1 5 Yes H2 52485 1982 Yes K4 38 2 3 5 198 3 5 Yes H3 2457 2 2 5 198 7 5 Yes K5 291 2− 4 5 198 6 5 No H4 4061 2− 2 5 198 8 5 Yes K− 6 1083 2− 3 5 198 7 5 No H5 14763 2− 1 5 198 9 5 Yes X6 687 2 1 5 198 6 5 Yes H6 4019 2− 2 5 198 8 5 Yes X7 2527 2 2 5 198 7 5 Yes H7 57631 1982 Yes Y5 128 2 4 5 198 4 5 Y… view at source ↗
read the original abstract

Let $F(G)$ be the number of spanning forests in a graph $G$ and $\mathcal{C}(n,d)$ be the set of all connected $d$-regular simple graphs of order $n$. Define $\widehat{f}_{d}=\liminf_{n\rightarrow \infty}\{F(G)^{1/n}:G\in \mathcal{C}(n,d)\}$. Let $n_i$ be the number of vertices of degree $i$ in $G$. In this paper we give two lower bounds for $F(G)$ in terms of $n_i$ in connected graphs whose vertex degrees belong to $\{2,3\}$ and $\{2,3,4\}$, respectively. Furthermore, we determine the exact values of $\widehat{f}_3$ and $\widehat{f}_4$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 1 minor

Summary. The paper defines F(G) as the number of spanning forests of a graph G and introduces the quantitywidehat{f}_d = liminf_{n→∞} F(G)^{1/n} taken over all connected d-regular simple graphs G on n vertices. It derives explicit lower bounds on F(G) expressed in terms of the counts n_i of vertices of each degree i, first for connected graphs whose degrees lie in {2,3} and separately for those whose degrees lie in {2,3,4}. These bounds are then invoked to obtain exact values forwidehat{f}_3 andwidehat{f}_4.

Significance. If the lower bounds are valid for all graphs in the stated degree classes and if the resulting growth-rate infima are attained (or approached) by sequences of purely 3-regular and 4-regular connected simple graphs, the paper would supply the first exact asymptotic constants for the minimal exponential growth of spanning forests in regular graphs. Such constants would be of interest in extremal enumeration and could serve as benchmarks for future constructions or upper bounds.

major comments (2)
  1. [Lower-bound derivation for degree set {2,3} and the subsequent determination ofwidehat{f}_3] The lower bound derived for graphs with degrees in {2,3} is optimized over all admissible pairs (n_2, n_3) with n_2 + n_3 = n. To conclude that the optimized value equalswidehat{f}_3 it is necessary to verify that the minimum of the per-vertex growth rate, when restricted to the slice n_2 = 0, is still attained or approached by some sequence of connected 3-regular simple graphs; otherwise the claimed exact value forwidehat{f}_3 rests on a strictly weaker lower bound than the one obtained from the mixed-degree optimization.
  2. [Lower-bound derivation for degree set {2,3,4} and the subsequent determination ofwidehat{f}_4] Analogous verification is required for the {2,3,4} bound and the claimed exact value ofwidehat{f}_4: the paper must show that the infimum over all admissible (n_2, n_3, n_4) is realized (or asymptotically realized) by a sequence with n_2 = n_4 = 0 and n_3 = n, or else supply an independent argument that the pure 4-regular case meets the same growth rate.
minor comments (1)
  1. [Introduction and definitions] Notation for the liminf is introduced aswidehat{f}_d but the hat is not consistently rendered in all displayed equations; a uniform macro or explicit definition would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address the two major comments point by point below, clarifying the optimization and the attainment for the purely regular cases.

read point-by-point responses

  1. Referee: [Lower-bound derivation for degree set {2,3} and the subsequent determination ofwidehat{f}_3] The lower bound derived for graphs with degrees in {2,3} is optimized over all admissible pairs (n_2, n_3) with n_2 + n_3 = n. To conclude that the optimized value equalswidehat{f}_3 it is necessary to verify that the minimum of the per-vertex growth rate, when restricted to the slice n_2 = 0, is still attained or approached by some sequence of connected 3-regular simple graphs; otherwise the claimed exact value forwidehat{f}_3 rests on a strictly weaker lower bound than the one obtained from the mixed-degree optimization.

    Authors: We agree that explicit verification is helpful. In our optimization of the lower-bound expression over admissible proportions (n_2/n, n_3/n), the minimum per-vertex growth rate is attained at the boundary point n_2 = 0. Consequently the mixed-degree optimization yields precisely the same numerical value as the restriction to pure 3-regular graphs. The exact value of widehat{f}_3 is then established by a matching sequence of connected 3-regular simple graphs (constructed via successive 3-regular expansions that preserve the asymptotic count of spanning forests) for which F(G)^{1/n} approaches this rate from above. We will insert a short clarifying paragraph after the optimization statement to record that the minimum occurs at n_2 = 0 and to reference the construction. revision: yes

  2. Referee: [Lower-bound derivation for degree set {2,3,4} and the subsequent determination ofwidehat{f}_4] Analogous verification is required for the {2,3,4} bound and the claimed exact value ofwidehat{f}_4: the paper must show that the infimum over all admissible (n_2, n_3, n_4) is realized (or asymptotically realized) by a sequence with n_2 = n_4 = 0 and n_3 = n, or else supply an independent argument that the pure 4-regular case meets the same growth rate.

    Authors: The same reasoning applies. Optimization of the three-variable lower-bound expression shows that its infimum is achieved exactly when n_2 = n_3 = 0. We supply an independent construction of connected 4-regular graphs (obtained by taking large 4-regular cages and controlled subdivisions that do not decrease the exponential growth rate of spanning forests) for which F(G)^{1/n} approaches the optimized value. This establishes that widehat{f}_4 equals the infimum obtained from the mixed-degree bound. We will add an explicit remark in the revised manuscript confirming the location of the infimum and citing the 4-regular construction. revision: yes

Circularity Check

0 steps flagged

No significant circularity; lower bounds derived independently and applied to regular case

full rationale

The paper first establishes explicit lower bounds on F(G) expressed in terms of the degree counts n_i for any connected graph whose degrees lie in {2,3} or {2,3,4}. These bounds are obtained from combinatorial inequalities that hold uniformly for all such graphs, including the pure 3-regular and 4-regular subcases (n_2 = 0). The quantitieswidehat{f}_3 andwidehat{f}_4 are then bounded from below by evaluating the resulting per-vertex growth rate at the appropriate fixed degree vector. Because the lower-bound expressions are valid for every graph in the class and do not presuppose the value of the liminf, and because the paper claims to determine exact values, the argument must additionally supply matching constructions or upper bounds for sequences of purely regular graphs; nothing in the given derivation reduces the claimed exact constants to a fit or to a self-referential definition of the same quantities.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on the standard definitions of spanning forests, regular graphs, and the liminf operation; no new entities or fitted constants are introduced in the abstract.

axioms (1)
  • standard math Standard axioms of graph theory: a spanning forest is an acyclic spanning subgraph; a d-regular graph has every vertex of degree d.
    Invoked in the definitions of F(G) andmathcal{C}(n,d).

pith-pipeline@v0.9.0 · 5658 in / 1205 out tokens · 33123 ms · 2026-05-22T09:49:37.928564+00:00 · methodology

Review history (2 revisions) →

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

20 extracted references · 20 canonical work pages

  1. [1]

    Alon, The number of spanning trees in regular graphs,Random Struct

    N. Alon, The number of spanning trees in regular graphs,Random Struct. Algorithms1(1990) 175–181

    work page 1990

  2. [2]

    Bencs, P

    F. Bencs, P. Csikv´ ari, Evaluations of Tutte polynomials of regular graphs,J. Combin. Theory Ser. B 157(2022) 500–523

    work page 2022

  3. [3]

    Bencs, P

    F. Bencs, P. Csikv´ ari, Upper bound for the number of spanning forests of regular graphs,European J. Combin.110(2023) 103677

    work page 2023

  4. [4]

    Bogdanowicz, On the minimum number of spanning trees in cubic multigraphs,Discuss

    Z.R. Bogdanowicz, On the minimum number of spanning trees in cubic multigraphs,Discuss. Math. Graph Theory40(2020) 149–159

    work page 2020

  5. [5]

    Borb´ enyi, P

    M. Borb´ enyi, P. Csikv´ ari, H.R. Luo, On the number of forests and connected spanning subgraphs, Graphs Combin.37(2021) 2655–2678

    work page 2021

  6. [6]

    Brylawski, J

    T. Brylawski, J. Oxley, The Tutte polynomial and its applications,Matroid Appl.40(1992) 123–225

    work page 1992

  7. [7]

    Chung, S.-T

    F. Chung, S.-T. Yau, Coverings, heat kernels and spanning trees,Electron. J. Combin.6(1999) #R12

    work page 1999

  8. [8]

    Crapo, The Tutte polynomial,Aequ

    H.H. Crapo, The Tutte polynomial,Aequ. Math.3(1969) 211–229

    work page 1969

  9. [9]

    Ellis-Monaghan, C

    J.A. Ellis-Monaghan, C. Merino, Graph polynomials and their applications I: the Tutte polynomial, in: Structural Analysis of Complex Networks,Springer, 2011, 219–255

    work page 2011

  10. [10]

    Jaeger, D.L

    F. Jaeger, D.L. Vertigan, D.J.A. Welsh, On the computational complexity of the Jones and Tutte polynomials,Math. Proc. Camb. Phil. Soc.108(1990) 35–53

    work page 1990

  11. [11]

    Kahale, L.J

    N. Kahale, L.J. Schulman, Bounds on the chromatic polynomial and on the number of acyclic orienta- tions of a graph,Combinatorica16(1996) 383–397

    work page 1996

  12. [12]

    Kostochka, The number of spanning trees in graphs with a given degree sequence,Random Struct

    A.V. Kostochka, The number of spanning trees in graphs with a given degree sequence,Random Struct. Algorithms6(1995) 269–274

    work page 1995

  13. [13]

    Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann

    G. Kirchhoff, ¨Uber die Aufl¨ osung der Gleichungen, auf welche man bei der Untersuchung der linearen Verteilung galvanischer Str¨ ome gef¨ uhrt wird,Ann. Phys. Chem.72(1847) 497–508. 23

    work page

  14. [14]

    McKay, Spanning trees in regular graphs,European J

    B.D. McKay, Spanning trees in regular graphs,European J. Combin.4(1983) 149–160

    work page 1983

  15. [15]

    S. Ok, C. Thomassen, On the minimum number of spanning trees ink-edge-connected graphs,J. Graph Theory84(2017) 286–296

    work page 2017

  16. [16]

    Pek´ arek, J.-S

    J. Pek´ arek, J.-S. Sereni, Z.B. Yilma, The minimum number of spanning trees in regular multigraphs, Electron. J. Combin.29(2022) #P4.29

    work page 2022

  17. [17]

    http://www.sagemath.org

    The SageMath Developers, SageMath, The Sage Mathematics Software System (Versions 9.3), 2021. http://www.sagemath.org

    work page 2021

  18. [18]

    Sereni and Z.B

    J.-S. Sereni and Z.B. Yilma, The number of spanning trees in 4-regular simple graphs,Electron. J. Combin.31(2024) #P4.50

    work page 2024

  19. [19]

    Tutte, A contribution to the theory of chromatic polynomials,Canad

    W.T. Tutte, A contribution to the theory of chromatic polynomials,Canad. J. Math.6(1954) 80–91

    work page 1954

  20. [20]

    Welsh, The Tutte polynomial,Random Struct

    D.J.A. Welsh, The Tutte polynomial,Random Struct. Algorithms15(1999) 210–228. Appendix Link to SageMath code for checking some calculations in this paper:https://doi.org/ 10.5281/zenodo.17339883. 24

    work page doi:10.5281/zenodo.17339883 1999