betaFeedback

WorksMathematics

Upper bounds for the number of spanning forests of a graph

Abstract

Let GG be a simple graph on nn vertices, and let F(G)F(G) denote the number of spanning forests of GG. Bencs and Csikvári proved that every rr-regular graph GG with r≥2r\ge 2 satisfies F(G)≤rnF(G)\le r^n. Motivated by this result, they conjectured that if GG has minimum degree at least 33, then F(G)≤∏i=1ndiF(G)\leq \prod_{i=1}^n d_i, where (d1,d2,…,dn)(d_1, d_2, \dots, d_n) is the degree sequence of GG. In this paper, we prove that graphs with minimum degree at least n/3n/3 (n≥7)(n\geq7) satisfy F(G)≤∏i=1ndiF(G)\leq \prod_{i=1}^n d_i. 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 G=(V(G),E(G))G=(V(G), E(G)) be a graph with vertex set V(G)={v1,v2,…,vn}V(G)=\{v_1,v_2,\ldots,v_n\} and edge set E(G)={e1,e2,…,em}E(G)=\{e_1,e_2,\ldots,e_m\}. The numbers of vertices and edges are denoted by ∣V(G)∣=n|V(G)|=n and ∣E(G)∣=m|E(G)|=m, respectively. If the number of edges of GG is m=0m=0, then GG is called an edgeless graph. For a vertex viv_i, let di=dG(vi)d_i=d_G(v_i) be its degree, that is, the number of edges incident with it. For v∈V(G)v \in V(G), let NG(v)N_G(v) denote the set of all vertices in GG adjacent to vv. Arranging all vertex degrees in nonincreasing order gives the degree sequence of GG, (d1,d2,…,dn)(d_1,d_2,\ldots,d_n), where d1≥d2≥⋯≥dnd_1 \ge d_2 \ge\cdots\ge d_n. If d1=d2=⋯=dn=rd_1=d_2=\cdots=d_n=r, then GG is called an rr-regular graph. If r=n−1r=n-1, then GG is called the complete graph of order nn, denoted by KnK_n. Let δ=dn\delta=d_n denote the minimum degree of GG. If V(G)V(G) can be partitioned into two nonempty disjoint sets V1(G)V_1(G) and V2(G)V_2(G), and the edges of the graph are precisely all possible edges joining vertices in these two sets, then GG is called a complete bipartite graph. When ∣V1(G)∣=s|V_1(G)| = s and ∣V2(G)∣=t|V_2(G)| = t, it is denoted by Ks,tK_{s,t}. The graph K1,tK_{1,t} (t≥1t \ge1) is a star, whose vertex of degree tt is its center. When t=1t = 1, either endpoint can serve as the center. The double star Dp,qD_{p,q} is obtained from two stars K1,pK_{1,p} (p≥1p \ge1) and K1,qK_{1,q} (q≥1q \ge1) by joining their centers with an edge. Let G(t1,t2,t3)G(t_1,t_2,t_3) denote the connected graph with n=t1+t2+t3+2n = t_1 + t_2 + t_3 + 2 vertices and m=t1+t2+2t3+1m = t_1 + t_2 + 2t_3 + 1 edges, obtained from the stars K1,t1+t3K_{1,t_1+t_3} and K1,t2+t3K_{1,t_2+t_3} by joining their centers and pairwise identifying t3t_3 leaves of K1,t1+t3K_{1,t_1+t_3} with t3t_3 leaves of K1,t2+t3K_{1,t_2+t_3}, where t1,t2≥0t_1,t_2 \ge0 and t3≥1t_3 \ge1.

For any subset S⊆V(G)S \subseteq V(G), retain all vertices in SS and all edges of GG both of whose endpoints belong to SS. The resulting subgraph is called the subgraph induced by SS and is denoted by G[S]G[S]. When S=∅S = \varnothing, we adopt the convention that G[∅]G[\varnothing] is the graph with 0 vertices. Deleting from GG the vertices in SS and all edges incident with these vertices yields the graph denoted by G−SG - S; that is, G−S=G[V(G)∖S]G - S = G[V(G) \setminus S]. In particular, when S={vi}S = \{v_i\}, we abbreviate G−{vi}G - \{v_i\} as G−viG - v_i. For any notation not defined here, we refer the reader to [8].

A spanning forest of GG is a subgraph (V(G),E′)(V(G),E') with E′⊆E(G)E' \subseteq E(G) that is acyclic; that is, it is obtained by retaining all vertices of GG and choosing an edge set E′⊆E(G)E' \subseteq E(G) such that (V(G),E′)(V(G),E') is acyclic. The set of all spanning forests of GG and its cardinality are denoted, respectively, by

F(G)={(V(G),E′):E′⊆E(G), (V(G),E′) is acyclic},F(G)=∣F(G)∣.\mathcal{F}(G) = \{(V(G),E') : E' \subseteq E(G),\ (V(G),E')\text{ is acyclic}\}, \qquad F(G) = |\mathcal{F}(G)|.

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 F(G)F(G) 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 GG be a graph on nn vertices. Then

F(G)≤∏i=1n(di+1).F(G) \le\prod_{i=1}^{n}(d_i+1).

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 GG be a graph on nn vertices that is rr-regular (r≥2r \ge2). Then

F(G)≤rn.F(G) \le r^n.

Based on the two theorems above, they proposed the following conjecture.

Conjecture 1.1. Let GG be a graph on nn vertices. If δ≥3\delta\ge3, then

F(G)≤∏i=1ndi.F(G) \le\prod_{i=1}^{n}d_i.

We investigate this conjecture and identify a class of graphs for which it holds.

Theorem 1.3. Let GG be a graph on n≥7n \ge7 vertices. If δ≥n/3\delta\ge n/3, then F(G)<∏i=1ndiF(G) < \prod_{i=1}^{n}d_i.

We also find a class of graphs that do not satisfy Conjecture 1.1. Let Ky1,y2K_{y_1,y_2} (y2>y1≥3y_2 > y_1 \ge3) be a complete bipartite graph whose vertex set is partitioned into V1(G)={vi:di=y2,1≤i≤y1+y2}V_1(G) = \{v_i : d_i = y_2, 1 \le i \le y_1 + y_2\} and V2(G)={vj:dj=y1,1≤j≤y1+y2}V_2(G) = \{v_j : d_j = y_1, 1 \le j \le y_1 + y_2\}. We now construct a class of spanning forests of Ky1,y2K_{y_1,y_2}. For each vertex in V2(G)V_2(G), independently choose either to remain isolated or to be joined to one vertex in V1(G)V_1(G). Each such vertex has y1+1y_1 + 1 choices, and the resulting spanning subgraph is necessarily a spanning forest. Hence F(Ky1,y2)≥(y1+1)y2F(K_{y_1,y_2}) \ge(y_1 + 1)^{y_2}, and thus

F(Ky1,y2)∏i=1ndi≥(y1+1)y2y1y1y2y2=1y2y1(y1+1y1)y2.\frac{F(K_{y_1,y_2})}{\prod_{i=1}^{n}d_i} \ge\frac{(y_1+1)^{y_2}}{y_1^{y_1}y_2^{y_2}}=\frac{1}{y_2^{y_1}}\left(\frac{y_1+1}{y_1}\right)^{y_2}.

Let y1y_1 be a fixed constant with y1≥3y_1 \ge3. Since, as y2→∞y_2 \to\infty, we have ln⁡y2/y2→0\ln y_2/y_2 \to0, it follows that, as y2→∞y_2 \to\infty,

1y2y1(y1+1y1)y2=ey2ln⁡(1+1y1)−y1ln⁡y2⟶+∞.\frac{1}{y_2^{y_1}}\left(\frac{y_1+1}{y_1}\right)^{y_2}=e^{y_2\ln\left(1+\frac{1}{y_1}\right)-y_1\ln y_2}\longrightarrow+\infty.

Therefore, for every fixed constant y1y_1, all sufficiently large integers y2y_2 satisfy

F(Ky1,y2)>∏i=1ndi.F(K_{y_1,y_2})>\prod_{i=1}^{n}d_i.

As a concrete example, consider K3,14K_{3,14}. Applying Stark’s exact enumeration formula for spanning forests of complete bipartite graphs [16], we obtain

F(K3,14)=13 186 891 776>13 124 466 936=143 314.F(K_{3,14})=13\,186\,891\,776>13\,124\,466\,936=14^3\,3^{14}.

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 GG be a graph on n≥1n \ge1 vertices. For 2≤i≤n2 \le i \le n, define ki=(di−i+1)+k_i=(d_i-i+1)_+ and hi=∑j=i+1i+ki1dj+1h_i=\sum_{j=i+1}^{i+k_i}\frac{1}{d_{j+1}}, where (x)+=max⁡{x,0}(x)_+=\max\{x,0\}, and ki=0k_i=0 gives hi=0h_i=0. Then

F(G)≤∏i=2n(di+1−2hi),(1)F(G)\le\prod_{i=2}^{n}(d_i+1-2h_i), \tag*{(1)}

with equality if and only if GG is isomorphic to an edgeless graph, a star K1,tK_{1,t} (t≥1t\ge1), a double star Dp,qD_{p,q}, a graph G(t1,t2,t3)G(t_1,t_2,t_3), 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 GG be a graph on nn vertices, and let L(G)L(G) be its Laplacian matrix, with eigenvalues λ1≥λ2≥⋯≥λn=0\lambda_1 \ge\lambda_2 \ge\cdots\ge\lambda_n=0. Let InI_n denote the identity matrix of order nn. Then

F(G)≤det⁡(In+L(G))=∏i=1n(1+λi),F(G)\le\det(I_n+L(G))=\prod_{i=1}^{n}(1+\lambda_i),

with equality if and only if GG 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 GG be a connected graph on n≥2n \ge2 vertices with algebraic connectivity μ=λn−1>0\mu= \lambda_{n-1} > 0 and τ(G)\tau(G) spanning trees. Then

F(G)≤τ(G)((1+μ−1)n−μ−n),(2)F(G) \le\tau(G)((1+\mu^{-1})^n-\mu^{-n}), \tag*{(2)}

with equality if and only if G≅K2G \cong K_2 or G≅K3G \cong K_3.

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 GG be a graph on nn vertices, and let L(G)L(G) be its Laplacian matrix. For 0≤k≤n−10 \le k \le n-1, write

Fk(G)={φ∈F(G):∣E(φ)∣=k},fk(G)=∣Fk(G)∣.\mathcal{F}_k(G)=\{\varphi\in\mathcal{F}(G): |E(\varphi)|=k\}, \qquad f_k(G)=|\mathcal{F}_k(G)|.

Let

det⁡(In+tL(G))=∑k=0n−1ck(G)tk,(3)\det(I_n+tL(G))=\sum_{k=0}^{n-1}c_k(G)t^k, \tag*{(3)}

then

ck(G)=∑φ∈Fk(G)∏T∈T(φ)∣V(T)∣,c_k(G)=\sum_{\varphi\in\mathcal{F}_k(G)}\prod_{T\in\mathcal{T}(\varphi)}|V(T)|,

where T(φ)\mathcal{T}(\varphi) denotes the set of all tree components of the forest φ\varphi. In particular, c0(G)=1c_0(G)=1.

We now prove Theorem 1.6.

Proof of Theorem 1.6: For a graph on nn vertices, denoted by GG, let φ∈Fk(G)\varphi\in\mathcal{F}_k(G) be a spanning forest of GG with kk edges, where 0≤k≤n−10 \le k \le n-1. Thus, ∣T(φ)∣=n−k|\mathcal{T}(\varphi)|=n-k. Let the orders of its tree components be s1,…,sn−ks_1,\ldots,s_{n-k}, and let sj′=sj−1≥0s'_j=s_j-1\ge0. Since the number of edges in each tree component is sj−1s_j-1, we have ∑j=1n−ksj′=k\sum_{j=1}^{n-k}s'_j=k. Therefore,

∏T∈T(φ)∣V(T)∣=∏j=1n−k(1+sj′)≥1+∑j=1n−ksj′=k+1.(4)\prod_{T\in\mathcal{T}(\varphi)}|V(T)|=\prod_{j=1}^{n-k}(1+s'_j)\ge1+\sum_{j=1}^{n-k}s'_j=k+1. \tag*{(4)}

If at least two of the sj′s'_j 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 sj′s'_j 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 0≤k≤n−10 \le k \le n-1, we have

ck(G)=∑φ∈Fk(G)∏T∈T(φ)∣V(T)∣≥(k+1)fk(G).(5)c_k(G)=\sum_{\varphi\in\mathcal{F}_k(G)}\prod_{T\in\mathcal{T}(\varphi)}|V(T)|\ge(k+1)f_k(G). \tag*{(5)}

The Laplacian matrix is real symmetric and positive semidefinite, and L(G)1=0L(G)\mathbf{1}=0, where 1\mathbf{1} denotes the n×1n\times1 vector whose entries are all 11. Therefore,

det⁡(In+tL(G))=∏i=1n(1+tλi).\det(I_n+tL(G))=\prod_{i=1}^{n}(1+t\lambda_i).

Combining (3) and (5) and integrating the preceding identity term by term yields

F(G)=∑k=0n−1fk(G)≤∑k=0n−1ck(G)k+1=∫01∑k=0n−1ck(G)tk dt=∫01∏i=1n(1+tλi) dt,(6)F(G)=\sum_{k=0}^{n-1}f_k(G)\le\sum_{k=0}^{n-1}\frac{c_k(G)}{k+1}=\int_0^1\sum_{k=0}^{n-1}c_k(G)t^k\,\mathrm{d}t=\int_0^1\prod_{i=1}^{n}(1+t\lambda_i)\,\mathrm{d}t, \tag*{(6)}

Equality holds in (6) if and only if every spanning forest of GG, denoted by φ\varphi, attains equality in (4), that is, φ\varphi has at most one component containing an edge, which is equivalent to the matching number of GG being at most one.

We now consider a connected graph on n≥2n\ge2 vertices, denoted by GG. By Lemma 2.1, we have ∏i=1n−1λi=cn−1(G)=nτ(G)\prod_{i=1}^{n-1}\lambda_i=c_{n-1}(G)=n\tau(G). For 1≤i≤n−11\le i\le n-1, we have λi≥μ>0\lambda_i\ge\mu>0. Combining this with (6) gives

F(G)≤nτ(G)∫01∏i=1n−1(t+λi−1) dt(7)F(G)\le n\tau(G)\int_0^1\prod_{i=1}^{n-1}(t+\lambda_i^{-1})\,\mathrm{d}t \tag*{(7)}
≤nτ(G)∫01(t+μ−1)n−1 dt=τ(G)((1+μ−1)n−μ−n).(8)\begin{aligned} \le n\tau(G)\int_0^1(t+\mu^{-1})^{n-1}\,\mathrm{d}t \\ &=\tau(G)\left((1+\mu^{-1})^n-\mu^{-n}\right). \tag*{(8)} \end{aligned}

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 λ1=⋯=λn−1=μ\lambda_1=\cdots=\lambda_{n-1}=\mu, so L(G)=μ(In−Jn/n)L(G)=\mu(I_n-J_n/n), where JnJ_n is the all-ones matrix. Since the off-diagonal entries of the Laplacian matrix L(G)L(G) can only be −1-1 or 00, we obtain μ=n\mu=n, that is, G≅KnG\cong K_n. Equality in (7) is equivalent to equality in (6), that is, the maximum matching of GG has at most 11 edge. Thus, equality holds in (2) if and only if G≅K2G\cong K_2 or G≅K3G\cong K_3. This completes the proof.

Proof of Theorem 1.3

To prove Theorem 1.3, we first introduce some lemmas.

Lemma 3.1. ([10]) Let MM be a real symmetric positive definite matrix of order n≥2n\ge2, with the following block form:

M=(azTzH)M=\begin{pmatrix}a & \mathbf{z}^{T}\\ \mathbf{z} & H\end{pmatrix}

where aa is a real number, z\mathbf{z} is an (n−1)×1(n-1)\times1 column vector, and HH is a matrix of order n−1n-1. Then

det⁡M≤adet⁡H≤a(tr⁡Hn−1)n−1,(9)\det M \le a\det H \le a\left(\frac{\operatorname{tr}H}{n-1}\right)^{n-1}, \tag*{(9)}

Equality in the first inequality holds if and only if z=0\mathbf{z}=0; equality in the second inequality holds if and only if HH is a positive real multiple of the identity matrix.

Lemma 3.2. Let GG be a graph on n≥2n\ge2 vertices with no isolated vertices. Define

Wn=(nn−1)n−1,β(G)=1n∑i=1n1di−12m.W_n=\binom{n}{n-1}^{n-1},\qquad\beta(G)=\frac{1}{n}\sum_{i=1}^{n}\frac{1}{d_i}-\frac{1}{2m}.

Then

F(G)∏i=1ndi≤Wn2m((1+β(G))n−β(G)n),(10)\frac{F(G)}{\prod_{i=1}^{n}d_i}\le\frac{W_n}{2m}\left((1+\beta(G))^n-\beta(G)^n\right), \tag*{(10)}

Equality in (10) holds if and only if G≅K2G\cong K_2 or G≅K3G\cong K_3.

Proof. Let D(G)=diag⁡(d1,…,dn)D(G)=\operatorname{diag}(d_1,\ldots,d_n) denote the degree matrix of GG, abbreviated as DD. Define

L=D−1/2L(G)D−1/2,Mt=D−1+tL.\mathcal{L}=D^{-1/2}L(G)D^{-1/2},\qquad M_t=D^{-1}+t\mathcal{L}.

Since L\mathcal{L} is positive semidefinite and D−1D^{-1} is positive definite, for every real number t≥0t\ge0, the matrix MtM_t is positive definite. Since D1/2LD1/2=L(G)D^{1/2}\mathcal{L}D^{1/2}=L(G), we have

D1/2MtD1/2=In+tL(G).(11)D^{1/2}M_tD^{1/2}=I_n+tL(G). \tag*{(11)}

Since det⁡(D)=∏i=1ndi\det(D)=\prod_{i=1}^{n}d_i, taking determinants on both sides of (11) gives

det⁡(Mt)=det⁡(In+tL(G))∏i=1ndi.(12)\det(M_t)=\frac{\det(I_n+tL(G))}{\prod_{i=1}^{n}d_i}. \tag*{(12)}

Let u=D1/212m\mathbf{u}=\frac{D^{1/2}\mathbf{1}}{\sqrt{2m}} be an n×1n\times1 column vector. Since

uTu=1TD12m=1,\mathbf{u}^{T}\mathbf{u}=\frac{\mathbf{1}^{T}D\mathbf{1}}{2m}=1,

u\mathbf{u} is a unit vector. Since

Lu=D−1/2L(G)D−1/2D1/212m=0,\mathcal{L}\mathbf{u}=\frac{D^{-1/2}L(G)D^{-1/2}D^{1/2}\mathbf{1}}{\sqrt{2m}}=0,

we have Mtu=(D−1+tL)u=D−1uM_t\mathbf{u}=(D^{-1}+t\mathcal{L})\mathbf{u}=D^{-1}\mathbf{u}. Let q=uTD−1uq=\mathbf{u}^{T}D^{-1}\mathbf{u}. Then

q=12m1TD1/2D−1D1/21=12m1T1=n2m.q=\frac{1}{2m}\mathbf{1}^{T}D^{1/2}D^{-1}D^{1/2}\mathbf{1} =\frac{1}{2m}\mathbf{1}^{T}\mathbf{1} =\frac{n}{2m}.

Let u⊥={x∈Rn:uTx=0}\mathbf{u}^{\perp}=\{\mathbf{x}\in\mathbb{R}^{n}:\mathbf{u}^{T}\mathbf{x}=0\}. Choose an n×(n−1)n\times(n-1) real matrix QQ whose columns form an orthonormal basis of u⊥\mathbf{u}^{\perp}. Then U=(u,Q)U=(\mathbf{u},Q) is an orthogonal matrix. Hence

UTMtU=(qbTbHt),q=uTD−1u=n2m,b=QTMtu=QTD−1u,Ht=QTMtQ.U^{T}M_tU= \begin{pmatrix} q & \mathbf{b}^{T}\\ \mathbf{b} & H_t \end{pmatrix}, \qquad q=\mathbf{u}^{T}D^{-1}\mathbf{u}=\frac{n}{2m}, \qquad \mathbf{b}=Q^{T}M_t\mathbf{u}=Q^{T}D^{-1}\mathbf{u}, \qquad H_t=Q^{T}M_tQ.

Since MtM_t is positive definite and the columns of QQ are linearly independent, HtH_t is also positive definite. Write s′=∑i=1ndi−1s'=\sum_{i=1}^{n}d_i^{-1}. Then

tr⁡(Mt)=tr⁡(D−1)+ttr⁡(L)=s′+nt.\operatorname{tr}(M_t)=\operatorname{tr}(D^{-1})+t\operatorname{tr}(L)=s'+nt.

Orthogonal similarity transformations preserve the trace of a matrix. Combining this with tr⁡(UTMtU)=q+tr⁡(Ht)\operatorname{tr}(U^T M_t U)=q+\operatorname{tr}(H_t), we obtain

tr⁡Ht=tr⁡Mt−q=s′+nt−n2m=n(t+β(G)).\operatorname{tr}H_t=\operatorname{tr}M_t-q=s'+nt-\frac{n}{2m}=n(t+\beta(G)).

Since H0H_0 is also positive definite, nβ(G)=tr⁡H0>0n\beta(G)=\operatorname{tr}H_0>0. By Lemma 3.1, we have

det⁡(UTMtU)=det⁡Mt≤n2m(n(t+β(G))n−1)n−1.\det(U^T M_t U)=\det M_t\leq\frac{n}{2m}\left(\frac{n(t+\beta(G))}{n-1}\right)^{n-1}.

Combining this with (12), we obtain, for every real number t≥0t\geq0,

det⁡(In+tL(G))∏i=1ndi≤n2mWn(t+β(G))n−1.(13)\frac{\det(I_n+tL(G))}{\prod_{i=1}^{n}d_i}\leq\frac{n}{2m}W_n(t+\beta(G))^{n-1}. \tag*{(13)}

From (6) and (13), we obtain

F(G)∏i=1ndi≤∫01det⁡(In+tL(G))∏i=1ndi dt(14)\frac{F(G)}{\prod_{i=1}^{n}d_i}\leq\int_0^1\frac{\det(I_n+tL(G))}{\prod_{i=1}^{n}d_i}\,dt \tag*{(14)}
≤n2mWn∫01(t+β(G))n−1 dt=Wn2m((1+β(G))n−β(G)n),(15)\begin{aligned} \leq\frac{n}{2m}W_n\int_0^1(t+\beta(G))^{n-1}\,dt \\ &=\frac{W_n}{2m}\left((1+\beta(G))^n-\beta(G)^n\right), \tag*{(15)} \end{aligned}

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,

∫01[n2mWn(t+β(G))n−1−det⁡(In+tL(G))∏i=1ndi] dt=0.\int_0^1\left[\frac{n}{2m}W_n(t+\beta(G))^{n-1}-\frac{\det(I_n+tL(G))}{\prod_{i=1}^{n}d_i}\right]\,dt=0.

By (13), the function in square brackets above is continuous and nonnegative on [0,1][0,1]. Hence, for every real number t′∈[0,1]t'\in[0,1], we have

nWn2m(t′+β(G))n−1=det⁡(In+t′L(G))∏i=1ndi.(16)\frac{nW_n}{2m}(t'+\beta(G))^{n-1}=\frac{\det(I_n+t'L(G))}{\prod_{i=1}^{n}d_i}. \tag*{(16)}

For (16) to hold, both equality conditions in (9) must be satisfied, namely, b=QTD−1u=0\mathbf{b}=Q^TD^{-1}\mathbf{u}=\mathbf{0} and HtH_t is a positive real multiple of the identity matrix. From b=0\mathbf{b}=\mathbf{0}, it follows that D−1uD^{-1}\mathbf{u} is parallel to u\mathbf{u}. Since GG has no isolated vertices and every coordinate of u\mathbf{u} is nonzero, all did_i are equal. Let di=rd_i=r; that is, GG is rr-regular. Taking t′=1t'=1, since H1H_1 is a positive real multiple of the identity matrix and M1=r−1In+r−1L(G)M_1=r^{-1}I_n+r^{-1}L(G), we obtain

L(G)=nrn−1(In−1nJn).L(G)=\frac{nr}{n-1}\left(I_n-\frac{1}{n}J_n\right).

Since every off-diagonal entry of the Laplacian matrix L(G)L(G) is either −1-1 or 00, we have r=n−1r=n-1, that is, G≅KnG\cong K_n. Equality in (14) holds if and only if equality holds in (6). Therefore, equality in (10) holds if and only if G≅K2G\cong K_2 or G≅K3G\cong K_3. This completes the proof.

We now prove Theorem 1.3.

Proof of Theorem 1.3: Let GG be a graph on n≥7n\ge7 vertices with δ≥n/3\delta\ge n/3. For a real number x>0x>0, define

Bn(x)=Wnnx[(1+n−1nx)n−(n−1nx)n].(17)B_n(x)=\frac{W_n}{nx}\left[\left(1+\frac{n-1}{nx}\right)^n-\left(\frac{n-1}{nx}\right)^n\right]. \tag*{(17)}

For every i(1≤i≤n)i(1\le i\le n), we have 0<di<2m0<d_i<2m. Combining 2m=∑i=1ndi≥nδ2m=\sum_{i=1}^{n}d_i\ge n\delta with the preceding relation, we obtain

nβ(G)=∑i=1n1−di/(2m)di≤1δ∑i=1n(1−di2m)=n−1δ.(18)n\beta(G)=\sum_{i=1}^{n}\frac{1-d_i/(2m)}{d_i}\le\frac{1}{\delta}\sum_{i=1}^{n}\left(1-\frac{d_i}{2m}\right)=\frac{n-1}{\delta}. \tag*{(18)}

The function f(x)=(1+x)n−xnf(x)=(1+x)^n-x^n is strictly increasing for x>0x>0, whereas n−1nx>0\frac{n-1}{nx}>0 and is strictly decreasing for x>0x>0. Therefore,

(1+n−1nx)n−(n−1nx)n\left(1+\frac{n-1}{nx}\right)^n-\left(\frac{n-1}{nx}\right)^n

is strictly decreasing for x>0x>0. Since Wnnx\frac{W_n}{nx} is also strictly decreasing for x>0x>0, Bn(x)B_n(x) is strictly decreasing for x>0x>0. Substituting (18) into (10) gives

F(G)∏i=1ndi≤Wn2m((1+β(G))n−β(G)n)≤Bn(δ).\frac{F(G)}{\prod_{i=1}^{n}d_i}\le\frac{W_n}{2m}\left((1+\beta(G))^n-\beta(G)^n\right)\le B_n(\delta).

Since Wn<eW_n<e and 1+x<ex1+x<e^x (x>0x>0), we have

Bn(δ)<enδ(1+n−1nδ)n<e1+(n−1)/δnδ.B_n(\delta)<\frac{e}{n\delta}\left(1+\frac{n-1}{n\delta}\right)^n<\frac{e^{1+(n-1)/\delta}}{n\delta}.

By the above discussion, either Bn(δ)<1B_n(\delta)<1 or ln⁡(nδ)≥1+n−1δ\ln(n\delta)\ge1+\frac{n-1}{\delta} guarantees that Conjecture 1.1 holds.

We first consider the case n≥12n\ge12. Since δ≥n/3\delta\ge n/3, we have

ln⁡(nδ)−1−n−1δ≥ln⁡(n2/3)−4+3n.\ln(n\delta)-1-\frac{n-1}{\delta}\ge\ln(n^2/3)-4+\frac{3}{n}.

Let h(x)=ln⁡(x2/3)−4+3xh(x)=\ln(x^2/3)-4+\frac{3}{x}. For x≥12x\ge12, we have h′(x)=(2x−3)/x2>0h'(x)=(2x-3)/x^2>0, and h(12)=ln⁡48−15/4>0h(12)=\ln48-15/4>0, so, for n≥12n\ge12, Conjecture 1.1 holds.

When 7≤n≤117\le n\le11, the integrality of the degrees gives δ≥⌈n/3⌉\delta\ge\lceil n/3\rceil. Direct substitution into (17) gives (with the results rounded to two decimal places) B7(3)=0.70B_7(3)=0.70, B8(3)=0.82B_8(3)=0.82, B9(3)=0.98B_9(3)=0.98, B10(4)=0.49B_{10}(4)=0.49, B11(4)=0.56B_{11}(4)=0.56. Thus, for all 7≤n≤117 \le n \le11, we have Bn(δ)<1B_n(\delta)<1, 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 GG, let P(G)\mathcal{P}(G) denote the set of its spanning pseudo-forests, let z(ψ)z(\psi) denote the number of unicyclic components of a pseudo-forest ψ\psi, and let T(ψ)\mathcal{T}(\psi) denote the set of its tree components. Let MM be a subset of E(G)E(G). If no two edges in MM are adjacent in GG, then MM is called a matching of GG. Let ∣M∣|M| denote the number of edges in MM, and let V(M)V(M) denote the set of all vertices covered by the matching MM. Let M(G)\mathcal{M}(G) denote the set of all matchings of GG (including the empty matching).

Lemma 4.1. Let GG be a graph on nn vertices. For each vertex vi∈V(G)v_i \in V(G), let did_i denote the degree of viv_i. Let ai≥0a_i \ge0 be the weight of viv_i, and let qi=di+1+aiq_i=d_i+1+a_i. Define

PG(q)=∑M∈M(G)(−2)∣M∣∏vi∈V(G)∖V(M)qi(19)P_G(\mathbf{q})=\sum_{M\in\mathcal{M}(G)}(-2)^{|M|}\prod_{v_i\in V(G)\setminus V(M)}q_i \tag*{(19)}

where q\mathbf{q} is the parameter vector, that is, q=(qi)vi∈V(G)\mathbf{q}=(q_i)_{v_i\in V(G)}. Then

PG(q)=∑ψ∈P(G)2z(ψ)∏T∈T(ψ)(1+∑vi∈V(T)ai)>0,(20)P_G(\mathbf{q})=\sum_{\psi\in\mathcal{P}(G)}2^{z(\psi)}\prod_{T\in\mathcal{T}(\psi)}\left(1+\sum_{v_i\in V(T)}a_i\right)>0, \tag*{(20)}

When V(G)=∅V(G)=\varnothing, both sides are taken to be 1.

Proof: Let ti′=1+ait_i'=1+a_i. Then qi=ti′+diq_i=t_i'+d_i. In (19), expand the term corresponding to a matching M′M' as follows: each matching edge vivjv_iv_j produces arrows vi→vjv_i\to v_j and vj→viv_j\to v_i; mark this pair of arrows and assign it weight −2-2. In the graph GG, for the matching M′M', each uncovered vertex viv_i has two choices: either choose a neighbor vjv_j and draw an arrow vi→vjv_i\to v_j, with weight 11, or choose no neighbor and draw no arrow, with weight ti′t_i'. The sum of the weights of all marked configurations obtained in this way is PG(q)P_G(\mathbf{q}). Denote the new graph obtained from GG by the above procedure by G′G'. A vertex of G′G' with no outgoing arrow is called a root of G′G'. In the graph G′G', let the total number of pairs of opposite arrows be bb.

Fix a graph G′G'. Each pair of opposite arrows can arise in two ways: either it is produced by a matching edge vivjv_iv_j; or, for the matching M′M', two uncovered vertices viv_i and vjv_j choose each other as neighbors and draw arrows vi→vjv_i\to v_j and vj→viv_j\to v_i, 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 J⊂{1,…,b}J\subset\{1,\ldots,b\} 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 (−2)∣J∣(-2)^{|J|}. Summing over all choices of markings gives

∑J⊂{1,…,b}(−2)∣J∣=∑k=0b(bk)(−2)k=(1−2)b=(−1)b,\sum_{J\subset\{1,\ldots,b\}}(-2)^{|J|}=\sum_{k=0}^{b}\binom{b}{k}(-2)^k=(1-2)^b=(-1)^b,

Each marking corresponds uniquely, in the graph GG, to a term for the original matching M′M' in the expansion in (19). Therefore,

PG(q)=∑G′(−1)b∏vi∈R(G′)ti′(21)P_G(\mathbf{q})=\sum_{G'}(-1)^b\prod_{v_i\in R(G')}t'_i \tag*{(21)}

Here we no longer distinguish whether the pairs of opposite arrows in G′G' arise from matching edges, and R(G′)R(G') denotes the set of all roots of G′G'.

Now retain only the edges of G′G' carrying arrows (deleting all edges without arrows), and then remove all arrows. In the spanning subgraph of G′G' obtained by this procedure, the number of edges in each connected component CC is at most the number of outgoing arrows, so ∣E(C)∣≤∣V(C)∣|E(C)|\leq|V(C)|. 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 CC is a tree TT, let s′s' be its number of vertices, r′r' its number of roots, and bTb_T its number of pairs of opposite arrows. Counting the total number of outgoing arrows in two ways gives s′−r′s'-r' and ∣E(T)∣+bT=s′−1+bT|E(T)|+b_T=s'-1+b_T, respectively. Hence r′=1−bTr'=1-b_T. Thus r′r' can only be 1 or 0: when r′=1r'=1, we have bT=0b_T=0. After choosing the unique root viv_i arbitrarily, all other edges must point toward this root along the unique paths in the tree, giving a total weight of ∑vi∈V(T)ti′\sum_{v_i\in V(T)}t'_i; when r′=0r'=0, we have bT=1b_T=1. After choosing the unique edge carrying opposite arrows arbitrarily, all other arrows must point toward this edge. Each choice has weight −1-1, giving a total weight of −∣E(T)∣-|E(T)|. Therefore, the total contribution of a tree component is

∑vi∈V(T)ti′−∣E(T)∣=1+∑vi∈V(T)ai.\sum_{v_i\in V(T)}t'_i-|E(T)|=1+\sum_{v_i\in V(T)}a_i.

If a connected component CC is unicyclic, let r′′r'' be its number of roots and bCb_C its number of pairs of opposite arrows. The same arrow count gives ∣V(C)∣−r′′=∣E(C)∣+bC=∣V(C)∣+bC|V(C)|-r''=|E(C)|+b_C=|V(C)|+b_C, so r′′=bC=0r''=b_C=0. 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 aia_i vanish, Lemma 4.1 reduces to the pseudo-forest expansion of the polynomial RG(z)R_G(z) at z=2z=2 given by Bencs and Csikvári [3, 4].

To illustrate Lemma 4.1, consider the graph G=G(1,0,1)G=G(1,0,1) (defined in the introduction), which is a triangle with one pendant edge, and set ai=0a_i=0 for every vertex. All 16 spanning subgraphs of GG 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 PG(q)=14+2⋅2=18P_G(\mathbf{q})=14+2\cdot2=18. In Eq. (19), the empty matching contributes 72, the four single-edge matchings together contribute −2(6+6+9+8)-2(6+6+9+8), and the unique two-edge matching contributes 4, yielding the same value.

Lemma 4.2. Let GG be a graph on nn vertices, and let HH be the graph obtained from GG by deleting

a vertex vv (v∈V(G)v \in V(G)). For each vi∈V(H)v_i \in V(H), let qi=di+1q_i = d_i + 1. For a vertex set S⊆V(H)S \subseteq V(H), define

Ri(S)=P(S)P(S∖{vi})(vi∈S),bi(S)=qi−2∑vj∈NH[S](vi)1qj.R_i(S) = \frac{P(S)}{P(S \setminus\{v_i\})} \quad(v_i \in S), \qquad b_i(S) = q_i - 2 \sum_{v_j \in N_{H[S]}(v_i)} \frac{1}{q_j}.

where P(S)=PH[S](q∣S)P(S) = P_{H[S]}(\mathbf{q}|_S), q∣S=(qi)vi∈S\mathbf{q}|_S = (q_i)_{v_i \in S}, and q∣S\mathbf{q}|_S inherits the weights from GG. Then

F(G)=∑φ∈F(H)∏T∈T(φ)(1+∣NG(v)∩V(T)∣)≤PH(q),(22)F(G) = \sum_{\varphi\in\mathcal{F}(H)} \prod_{T \in\mathcal{T}(\varphi)} \left(1 + |N_G(v) \cap V(T)|\right) \leq P_H(\mathbf{q}), \tag*{(22)}
0<Ri(S)=qi−2∑vj∈NH[S](vi)1Rj(S∖{vi})≤qi;(23)0 < R_i(S) = q_i - 2 \sum_{v_j \in N_{H[S]}(v_i)} \frac{1}{R_j(S \setminus\{v_i\})} \leq q_i; \tag*{(23)}
Ri(S)≤bi(S),bi(S)≥1,(24)R_i(S) \leq b_i(S), \qquad b_i(S) \geq1, \tag*{(24)}

Equality in (22) holds if and only if HH is a forest.

Proof: For HH, fix a spanning forest φ\varphi. We now add the vertex vv back to obtain spanning forests of GG. In φ\varphi, fix a tree component TiT_i, and let the number of its vertices adjacent to vv be

ai′=∣NG(v)∩V(Ti)∣.a'_i = |N_G(v) \cap V(T_i)|.

There are two types of extensions for this tree component: the first is not to connect it to vv, for which there is only 1 possibility; the second is to connect one vertex of TiT_i to vv, for which there are ai′a'_i possibilities. If TiT_i has 2 or more vertices connected to vv, a cycle is formed, contrary to the definition of a spanning forest. The two choices are mutually exclusive, so there are 1+ai′=1+∣NG(v)∩V(Ti)∣1 + a'_i = 1 + |N_G(v) \cap V(T_i)| choices in total. Thus, for the fixed φ\varphi, the number of spanning forests of GG obtained is

∏T∈T(φ)(1+∣NG(v)∩V(T)∣).\prod_{T \in\mathcal{T}(\varphi)} \left(1 + |N_G(v) \cap V(T)|\right).

For any spanning forest of GG, deleting the vertex vv and its incident edges uniquely determines a spanning forest of HH, denoted by φ\varphi. Conversely, given φ\varphi and the choices above for each of its tree components, a spanning forest of GG is uniquely determined. Hence there is a bijection between the spanning forests of GG and all φ\varphi together with the above choices. Summing over F(H)\mathcal{F}(H) gives

F(G)=∑φ∈F(H)∏T∈T(φ)(1+∣NG(v)∩V(T)∣).F(G) = \sum_{\varphi\in\mathcal{F}(H)} \prod_{T \in\mathcal{T}(\varphi)} \left(1 + |N_G(v) \cap V(T)|\right).

The above analysis shows that, for each vi∈V(H)v_i \in V(H),

qi=dH(vi)+1+εi,εi=1{vvi∈E(G)}≥0.q_i = d_H(v_i) + 1 + \varepsilon_i, \qquad\varepsilon_i = \mathbf{1}_{\{vv_i \in E(G)\}} \geq0.

Applying Lemma 4.1 gives ai=di−dH(vi)a_i = d_i - d_H(v_i), and hence 1+∑vi∈V(T)ai=1+∣NG(v)∩V(T)∣1 + \sum_{v_i \in V(T)} a_i = 1 + |N_G(v) \cap V(T)|. Thus the sum in (22) consists of exactly all the forest terms in (20). Therefore, F(G)≤PH(q)F(G) \leq P_H(\mathbf{q}), with equality in (22) if and only if HH is a forest.

For any vertex set S⊆V(H)S \subseteq V(H) and vi∈Sv_i \in S, let ai=qi−dH[S](vi)−1=di−dH[S](vi)≥0a_i = q_i - d_{H[S]}(v_i) - 1 = d_i - d_{H[S]}(v_i) \geq0. By Lemma 4.1, both P(S)P(S) and P(S∖{vi})P(S \setminus\{v_i\}) are greater than 0, so Ri(S)>0R_i(S) > 0. We divide the matchings of H[S]H[S] into two classes according to whether they cover the vertex viv_i, and use (19) to derive a recurrence for P(S)P(S). First, consider matchings that do not cover the vertex viv_i. In this case, viv_i contributes a weight of qiq_i to the weighted sum over matchings. The matching on the remaining vertices can be any matching of H[S∖{vi}]H[S \setminus\{v_i\}]. Thus the total contribution of this class of matchings is qiP(S∖{vi})q_iP(S \setminus\{v_i\}). Next, consider matchings that cover the vertex viv_i. In this case, exactly one matching edge is incident with viv_i. Let this edge be vivjv_iv_j; it contributes a weight of −2-2. Since both viv_i and vjv_j are covered by this matching edge, the remaining matching edges can only be chosen from the graph H[S∖{vi,vj}]H[S \setminus\{v_i,v_j\}]. Therefore, for a fixed vjv_j, the total contribution of these matchings is −2P(S∖{vi,vj})-2P(S \setminus\{v_i,v_j\}). For viv_i, summing over all its neighbors vjv_j gives

−2∑vj∈NH[S](vi)P(S∖{vi,vj}).-2\sum_{v_j\in N_{H[S]}(v_i)}P(S\setminus\{v_i,v_j\}).

Combining the two cases above, we obtain

P(S)=qiP(S∖{vi})−2∑vj∈NH[S](vi)P(S∖{vi,vj}).(25)P(S)=q_iP(S\setminus\{v_i\})-2\sum_{v_j\in N_{H[S]}(v_i)}P(S\setminus\{v_i,v_j\}). \tag*{(25)}

Dividing both sides of (25) by P(S∖{vi})P(S \setminus\{v_i\}) gives (23). In S∖{vi}S \setminus\{v_i\}, take the vertex vjv_j, apply (23), and take reciprocals to obtain

1Rj(S∖{vi})≥1qj.\frac{1}{R_j(S\setminus\{v_i\})}\ge\frac{1}{q_j}.

Substituting this into (23) gives Ri(S)≤bi(S)R_i(S)\le b_i(S). For the vertex viv_i and any of its neighbors vjv_j in the sum, since dj≥1d_j\ge1, we have qj≥2q_j\ge2. Hence

bi(S)=qi−∑vj∈NH[S](vi)2qj≥qi−∑vj∈NH[S](vi)1=di+1−dH[S](vi)≥1.b_i(S)=q_i-\sum_{v_j\in N_{H[S]}(v_i)}\frac{2}{q_j}\ge q_i-\sum_{v_j\in N_{H[S]}(v_i)}1=d_i+1-d_{H[S]}(v_i)\ge1.

This completes the proof.

We now prove Theorem 1.4.

Proof of Theorem 1.4: When n=1n=1, GG is edgeless, F(G)=1F(G)=1, and the right-hand side of (1) is also 1. Thus Theorem 1.4 clearly holds. Henceforth, assume n≥2n\ge2.

For 2≤i≤n2\le i\le n, let qi=di+1q_i=d_i+1, Si={vi,…,vn}S_i=\{v_i,\ldots,v_n\}, Sn+1=∅S_{n+1}=\varnothing. Let H′=G−v1H'=G-v_1. In Lemma 4.2, take v=v1v=v_1 and H=H′H=H'. We retain its notation P(S)P(S) and Ri(S)R_i(S), with qiq_i always equal to di+1d_i+1. By (22), we obtain

F(G)≤PH′(q)=∏i=2nP(Si)P(Si+1)=∏i=2nRi(Si).(26)F(G)\le P_{H'}(\mathbf{q})=\prod_{i=2}^{n}\frac{P(S_i)}{P(S_{i+1})}=\prod_{i=2}^{n}R_i(S_i). \tag*{(26)}

Write

Ni={j:j>i and vivj∈E(G)},bi=qi−2∑j∈Ni1qj.N_i=\{j:j>i\text{ and }v_iv_j\in E(G)\},\qquad b_i=q_i-2\sum_{j\in N_i}\frac{1}{q_j}.

By (24), we have

0<Ri(Si)≤bi,bi≥1.(27)0<R_i(S_i)\le b_i,\qquad b_i\ge1. \tag*{(27)}

The neighbors of viv_i among v1,…,vi−1v_1,\ldots,v_{i-1} number at most i−1i-1. Hence

∣Ni∣≥max⁡{di−(i−1),0}=ki.|N_i| \ge\max\{d_i-(i-1),0\}=k_i.

Since q2≥q3≥⋯≥qn>0q_2 \ge q_3 \ge\cdots\ge q_n > 0, we have

1q2≤1q3≤⋯≤1qn.\frac{1}{q_2}\le\frac{1}{q_3}\le\cdots\le\frac{1}{q_n}.

If ki>0k_i>0, arrange the elements of NiN_i in increasing order as j1<⋯<j∣Ni∣j_1<\cdots<j_{|N_i|}. Then jℓ≥i+ℓj_\ell\ge i+\ell, so

∑j∈Ni1qj≥∑ℓ=1ki1qjℓ≥∑ℓ=1ki1qi+ℓ=hi.(28)\sum_{j\in N_i}\frac{1}{q_j}\ge\sum_{\ell=1}^{k_i}\frac{1}{q_{j_\ell}}\ge\sum_{\ell=1}^{k_i}\frac{1}{q_{i+\ell}}=h_i. \tag*{(28)}

When ki=0k_i=0, the corresponding hi=0h_i=0. Hence, for every ki≥0k_i\ge0, we have

∑j∈Ni1qj≥hi.(29)\sum_{j\in N_i}\frac{1}{q_j}\ge h_i. \tag*{(29)}

Therefore, for every i≥2i\ge2, we have

1≤bi≤qi−2hi=di+1−2hi.(30)1\le b_i\le q_i-2h_i=d_i+1-2h_i. \tag*{(30)}

All factors in (26), (27), and (30) are positive, so the inequalities can be multiplied term by term to give

F(G)≤∏i=2nbi≤∏i=2n(di+1−2hi).F(G)\le\prod_{i=2}^{n}b_i\le\prod_{i=2}^{n}(d_i+1-2h_i).

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 GG is not edgeless. Then d2≥1d_2\ge1. By (26), (27), and (30), for every 2≤i≤n2\le i\le n, we have

Ri(Si)=bi,∑j∈Ni1qj=hi.R_i(S_i)=b_i,\qquad\sum_{j\in N_i}\frac{1}{q_j}=h_i.

Equality in (29) requires ∣Ni∣=ki|N_i|=k_i. Thus, when ki=0k_i=0, we have Ni=∅N_i=\varnothing. When ki>0k_i>0, term-by-term comparison gives

djℓ=di+ℓ,1≤ℓ≤ki.(31)d_{j_\ell}=d_{i+\ell},\qquad1\le\ell\le k_i. \tag*{(31)}

On the other hand, (23) gives

bi−Ri(Si)=2∑j∈Ni(1Rj(Si+1)−1qj)=0,b_i-R_i(S_i)=2\sum_{j\in N_i}\left(\frac{1}{R_j(S_{i+1})}-\frac{1}{q_j}\right)=0,

Thus, for every j∈Nij\in N_i, we have Rj(Si+1)=qjR_j(S_{i+1})=q_j. For Rj(Si+1)R_j(S_{i+1}), applying (23) again gives

NG[Si+1](vj)=∅,j∈Ni.N_{G[S_{i+1}]}(v_j)=\varnothing,\qquad j\in N_i.

Since ∣N2∣=k2=d2−1|N_2|=k_2=d_2-1, we have v1v2∈E(G)v_1v_2 \in E(G). We consider two cases for d2d_2: if d2=1d_2=1, then for all i≥3i\ge3, we have di≤1d_i\le1; if d2≥2d_2\ge2, then k2>0k_2>0, and for each j∈N2j\in N_2, the corresponding vertex vjv_j is isolated in G[S3]G[S_3], so its neighbors can only belong to {v1,v2}\{v_1,v_2\}, and hence dj≤2d_j\le2. In (31), taking i=2i=2 and ℓ=1\ell=1, and using the equality conditions in (23), (27), and (28), we obtain d3=dj1≤2d_3=d_{j_1}\le2 (where j1j_1 is the smallest index in N2N_2). Thus, for all i≥3i\ge3, we have

∣Ni∣=ki=(di−i+1)+=0,|N_i|=k_i=(d_i-i+1)_+=0,

Hence G−{v1,v2}G-\{v_1,v_2\} is edgeless. Among the vertices of V(G)∖{v1,v2}V(G)\setminus\{v_1,v_2\}, let t1,t2,t3t_1,t_2,t_3 denote the numbers of vertices adjacent only to v1v_1, only to v2v_2, and to both v1,v2v_1,v_2, respectively. All remaining vertices are isolated. If t3≥1t_3\ge1, the graph obtained after deleting the isolated vertices is precisely G(t1,t2,t3)G(t_1,t_2,t_3). If t3=0t_3=0 and t1,t2≥1t_1,t_2\ge1, the resulting graph is the double star Dt1,t2D_{t_1,t_2}. If t3=0t_3=0 and at least one of t1,t2t_1,t_2 is 0, the resulting graph is the star K1,t1+t2+1K_{1,t_1+t_2+1}. This proves necessity.

Next, we prove sufficiency. If GG is edgeless, then F(G)=1F(G)=1, and every factor on the right-hand side of (1) is 1, so equality holds.

For the star K1,tK_{1,t}, the number of spanning forests is F(K1,t)=2t=2n−1F(K_{1,t})=2^t=2^{n-1}. Since di=1d_i=1 (2≤i≤n)(2\le i\le n) and ki=hi=0k_i=h_i=0 (2≤i≤n)(2\le i\le n), we have ∏i=2n(di+1−2hi)=2n−1\prod_{i=2}^{n}(d_i+1-2h_i)=2^{n-1}, that is,

F(K1,t)=∏i=2n(di+1−2hi).F(K_{1,t})=\prod_{i=2}^{n}(d_i+1-2h_i).

For the double star Dp,qD_{p,q} (p≥q)(p\ge q), the number of spanning forests is F(Dp,q)=2p+q+1=2n−1F(D_{p,q})=2^{p+q+1}=2^{n-1}. Since

d2=q+1,di=1 (3≤i≤n),k2=q,h2=q2,ki=hi=0 (3≤i≤n),d_2=q+1,\qquad d_i=1\ (3\le i\le n),\qquad k_2=q,\qquad h_2=\frac{q}{2},\qquad k_i=h_i=0\ (3\le i\le n),

we have ∏i=2n(di+1−2hi)=2n−1\prod_{i=2}^{n}(d_i+1-2h_i)=2^{n-1}, that is,

F(Dp,q)=∏i=2n(di+1−2hi).F(D_{p,q})=\prod_{i=2}^{n}(d_i+1-2h_i).

Without loss of generality, assume that t1≥t2t_1\ge t_2. Upon deleting the t1+t2t_1+t_2 pendant vertices, the graph G(t1,t2,t3)G(t_1,t_2,t_3) reduces to G(0,0,t3)G(0,0,t_3), namely the book graph consisting of t3t_3 triangles sharing a common edge. By [15],

F(G(0,0,t3))=2⋅3t3+t33t3−1.F(G(0,0,t_3))=2\cdot3^{t_3}+t_3 3^{t_3-1}.

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,

F(G(t1,t2,t3))=2t1+t2(2⋅3t3+t33t3−1)=2t1+t23t3(2+t33).F(G(t_1,t_2,t_3))=2^{t_1+t_2}\left(2\cdot3^{t_3}+t_3 3^{t_3-1}\right)=2^{t_1+t_2}3^{t_3}\left(2+\frac{t_3}{3}\right).

Since

d2=t2+t3+1,di=2 (3≤i≤t3+2),di=1 (t3+3≤i≤n),d_2=t_2+t_3+1,\qquad d_i=2\ (3\le i\le t_3+2),\qquad d_i=1\ (t_3+3\le i\le n),

we have

k2=t2+t3,h2=t33+t22,ki=hi=0(3≤i≤n),k_2=t_2+t_3,\qquad h_2=\frac{t_3}{3}+\frac{t_2}{2},\qquad k_i=h_i=0\quad(3\le i\le n),

that is,

∏i=2n(di+1−2hi)=(t2+t3+2−2t33−t2)3t32t1+t2=2t1+t23t3(2+t33)=F(G).\prod_{i=2}^{n}(d_i+1-2h_i)=\left(t_2+t_3+2-\frac{2t_3}{3}-t_2\right)3^{t_3}2^{t_1+t_2}=2^{t_1+t_2}3^{t_3}\left(2+\frac{t_3}{3}\right)=F(G).

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 nn vertices and mm edges is one of the bounds smaller than the other?

For convenience of comparison, for any connected graph with n≥2n\ge2 vertices and mm edges, denoted by GG, write

Ud(G)=∏i=2n(di+1−2hi),Uμ(G)=τ(G)((1+μ−1)n−μ−n).U_d(G)=\prod_{i=2}^{n}(d_i+1-2h_i),\qquad U_\mu(G)=\tau(G)\left((1+\mu^{-1})^n-\mu^{-n}\right).

We use several graph classes below to show that neither of these two upper bounds is uniformly better than the other.

For t≥2t\ge2, the star K1,tK_{1,t} has algebraic connectivity 11, and hence

Ud(K1,t)=F(K1,t)=2n−1<2n−1=Uμ(K1,t).U_d(K_{1,t})=F(K_{1,t})=2^{n-1}<2^n-1=U_\mu(K_{1,t}).

For the double star Dp,qD_{p,q} and, when n≥4n\ge4, the graph G(t1,t2,t3)G(t_1,t_2,t_3), equality holds in Theorem 1.4, but not in Theorem 1.6, and therefore

Ud(Dp,q)=F(Dp,q)<Uμ(Dp,q),U_d(D_{p,q})=F(D_{p,q})<U_\mu(D_{p,q}),
Ud(G(t1,t2,t3))=F(G(t1,t2,t3))<Uμ(G(t1,t2,t3)).U_d(G(t_1,t_2,t_3))=F(G(t_1,t_2,t_3))<U_\mu(G(t_1,t_2,t_3)).

For s≥2s\ge2, a calculation for the complete bipartite graph Ks,sK_{s,s} gives

Ud(Ks,s)=(s+1)s∏i=2s(s+1−2(s−i+1)s+1)=(s+1)2s−1∏j=1s−1(1−2j(s+1)2).U_d(K_{s,s})=(s+1)^s\prod_{i=2}^{s}\left(s+1-\frac{2(s-i+1)}{s+1}\right)=(s+1)^{2s-1}\prod_{j=1}^{s-1}\left(1-\frac{2j}{(s+1)^2}\right).

For 0≤xj≤10\le x_j\le1, we have ∏j(1−xj)≥1−∑jxj\prod_j(1-x_j)\ge1-\sum_jx_j, and applying this to the expression above gives

∏j=1s−1(1−2j(s+1)2)≥1−s(s−1)(s+1)2=3s+1(s+1)2.\prod_{j=1}^{s-1}\left(1-\frac{2j}{(s+1)^2}\right)\ge1-\frac{s(s-1)}{(s+1)^2}=\frac{3s+1}{(s+1)^2}.

Thus,

(3s+1)(s+1)2s−3≤Ud(Ks,s).(3s+1)(s+1)^{2s-3} \le U_d(K_{s,s}).

The Laplacian eigenvalues of the complete bipartite graph Ks,sK_{s,s} are

2s,s,…,s⏟2s−2 copies,0,2s,\quad\underbrace{s,\ldots,s}_{2s-2\ \text{copies}},\quad0,

so its algebraic connectivity is ss. From nτ(G)=∏i=1n−1λin\tau(G)=\prod_{i=1}^{n-1}\lambda_i, we obtain τ(Ks,s)=s2s−2\tau(K_{s,s})=s^{2s-2}, and therefore

Uμ(Ks,s)=s2s−2((1+1s)2s−1s2s)=(s+1)2s−1s2.U_\mu(K_{s,s})=s^{2s-2}\left(\left(1+\frac{1}{s}\right)^{2s}-\frac{1}{s^{2s}}\right)=\frac{(s+1)^{2s}-1}{s^2}.

Moreover, since

s2(3s+1)−(s+1)3=(s−2)(2s2+2s+1)+1>0,s^2(3s+1)-(s+1)^3=(s-2)(2s^2+2s+1)+1>0,

we have

Uμ(Ks,s)<(s+1)2ss2<(3s+1)(s+1)2s−3≤Ud(Ks,s).U_\mu(K_{s,s})<\frac{(s+1)^{2s}}{s^2}<(3s+1)(s+1)^{2s-3}\le U_d(K_{s,s}).

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. [1]D. Aldous, R. Lyons, Processes on unimodular random networks, Electron. J. Probab. 12 (2007) 1454–1508.arxiv.org/abs/math/0603062
  2. [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. [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. [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. [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. [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. [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. [8]R. Diestel, Graph theory, fifth ed. , in: Graduate Texts in Mathematics, vol. 173, Springer, Berlin, 2017, p. xviii+428.
  9. [9]G.R. Grimmett, S.N. Winkler, Negative association in uniform forests and connected graphs, Random Struct. Algorithms 24 (2004) 444–460.DOI
  10. [10]R.A. Horn, C.R. Johnson, Matrix Analysis, second ed., Cambridge University Press, Cambridge, 2013.
  11. [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. [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. [13]C.J. Liu, Y. Chow, Enumeration of forests in a graph, Proc. Amer. Math. Soc. 83 (1981) 659–662.DOI
  14. [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. [15]S. Shteiner, P. Shteyner, Comparing the numbers of subforests and subgraph-degree-tuples, arXiv:2510.26936v1 (2025).arxiv.org/abs/2510.26936
  16. [16]D. Stark, The asymptotic number of spanning forests of complete bipartite labelled graphs, Discrete Math. 313 (2013) 1256–1261.DOI
  17. [17]Y. Teranishi, The number of spanning forests of a graph, Discrete Math. 290 (2005) 259–267.DOI
  18. [18]C. Thomassen, Spanning trees and orientations of graphs, J. Comb. 1 (2010) 101–111.DOI
  19. [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. [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

Paper details

vlnc:W_qs4yxm2t
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents