1 Introduction↩︎

For a finite graph \(G\), let \(\tau(G)\) denote the number of spanning trees of \(G\). For a family of simple graphs \(\mathcal{G}\), we define its spanning-tree spectrum to be \[\mathcal{T}(\mathcal{G}) := \left\{\tau(G): G \in \mathcal{G}\right\}.\] In this paper, we study the spanning-tree spectrum of the family of simple graphs on \(n\) vertices: \[\mathcal{T}_n:=\left\{\tau(G): G \text{ is a simple graph on } n \text{ vertices}\right\}.\] By Cayley’s formula, every simple graph on \(n\) vertices has at most \(n^{n-2}\) spanning trees, and therefore \[\left|\mathcal{T}_n\right|\le n^{n-2}+1=\exp\bigl((1+o(1))n\log n\bigr).\] The main result of this paper gives a lower bound of the same shape.

1.1 Background↩︎

The problem of understanding the size of the spanning-tree spectrum goes back to Sedláček, who initiated the study of spanning-tree spectra for several natural graph classes, including all simple graphs, planar graphs, and regular graphs [1]–[4] in the late 1960s. The question was also recorded early in Moon’s monograph on labelled trees [5]. Until recently, however, even proving exponential growth for the spanning-tree spectrum of planar graphs was open.

Let \(\mathcal{G}_n^{\rm pl}\) denote the family of connected simple planar graphs on \(n\) vertices. Since a planar graph on \(n\geq 3\) vertices has at most \(3n-6\) edges, \(\tau(G) \leq \binom{3n-6}{n-1}\) for \(G\in \mathcal{G}_n^{\rm pl}\). Thus, the spanning-tree spectrum for planar graphs grows at most exponentially in \(n\); the current best known upper bound is \(5.2852^n\) due to Buchin–Schulz [6]. On the lower-bound side, Sedláček [2] proved a polynomial lower bound, namely \[\left|\mathcal{T}(\mathcal{G}_n^{\rm pl})\right|=\Omega(n^2),\] and Azarija [7] improved this to \[\left|\mathcal{T}(\mathcal{G}_n^{\rm pl})\right|\ge 2^{\Omega(\sqrt{n/\log n})}.\] A result of Stong [8] on the dual problem of constructing small graphs with a prescribed number of spanning trees implies the stronger bound \[\left|\mathcal{T}(\mathcal{G}_n^{\rm pl})\right|\ge 2^{\Omega(n^{2/3})}.\] In a remarkable paper, the exponential growth of the spanning-tree spectrum of planar graphs was finally settled in the affirmative by Chan–Kontorovich–Pak [9], who proved that \[\left|\mathcal{T}(\mathcal{G}_n^{\rm pl})\right|\ge 1.1103^n\] for all sufficiently large \(n\). Their argument combines a deletion–contraction construction for marked planar graphs, continued-fraction machinery, and Diophantine input related to Zaremba’s conjecture.

Subsequently, Alon–Bucić–Gishboliner [10] gave a short, purely combinatorial proof of the stronger bound \[\left|\mathcal{T}(\mathcal{G}_n^{\rm pl})\right|\ge 1.55^n.\] In the same work, they also proved that, for every fixed \(k\ge3\), the spanning-tree spectrum of connected \(k\)-regular graphs on \(n\) vertices has exponential size whenever \(kn\) is even, determining the correct growth order in another problem first raised by Sedláček.

The unrestricted simple-graph case is qualitatively different. For planar graphs, and more generally for graph families with bounded average degree, the number of spanning trees of an \(n\)-vertex graph is at most exponential in \(n\). For all simple graphs, however, Cayley’s formula leaves open the much larger scale \[\left|\mathcal{T}_n\right|\le n^{n-2}+1=\exp((1+o(1))n\log n).\] Until now, no lower bound on this larger scale was known. As Alon–Bucić–Gishboliner [10] point out, it was “somewhat remarkable” that, historically, the essentially best known lower bounds for the unrestricted spanning-tree spectrum all came from planar constructions, despite the much greater freedom available in arbitrary simple graphs. In particular, any superexponential lower bound for \(\left|\mathcal{T}_n\right|\) must use genuinely non-planar degrees of freedom.

This makes it natural to conjecture that the unrestricted spectrum has the same \(n\log n\) order as the Cayley upper bound. Chan–Kontorovich–Pak made this explicit in [9], conjecturing that \[\left|\mathcal{T}_n\right|=\exp(\Omega(n\log n)).\] 1 proves this conjecture.

It is useful to compare this with the corresponding range problem for \(0\)-\(1\) determinants. Let \(\sigma(n)\) be the set of positive values attained by determinants of \(n\times n\) matrices with entries in \(\{0,1\}\), and let \(b(n)\) be the largest integer such that \[\{1,2,\dots,b(n)\}\subseteq \sigma(n).\] Hadamard’s inequality gives the upper bound \[|\sigma(n)|,\;b(n)\le \exp\bigl((1/2+o(1))n\log n\bigr).\] In a recent breakthrough, Shitov [11] proved that this upper bound is sharp up to the lower-order term in the exponent: for all sufficiently large \(n\), \[\{0,1,\dots,\lfloor \exp(0.5\,n\log n-7n\log\log n) \rfloor\}\] is contained in the set of determinants of \(n\times n\) \(0\)-\(1\) matrices. Thus the \(0\)-\(1\) determinant problem has been solved not only for the size of the range, but also in the stronger interval sense, and with the correct constant in the exponent.

By Kirchhoff’s Matrix–Tree Theorem, spanning-tree counts are also determinant values, but of a much more constrained kind: they are determinants of Laplacian cofactors of simple graphs. In this sense, 1 may be viewed as a Matrix–Tree analogue of the \(0\)-\(1\) determinant range problem, in that it proves the correct \(n\log n\) order for the size of the range. There are, however, two important respects in which the graph problem remains less understood. First, our constant \(1/4\) is not expected to be sharp; the trivial Cayley upper bound allows the leading constant \(1\). Second, unlike Shitov’s theorem for \(0\)-\(1\) determinants, our construction does not produce a long initial interval of spanning-tree counts.

The interval question is closely related to the dual form of Sedláček’s problem. If \(\alpha'(t)\) denotes the least number of vertices in a simple graph with exactly \(t\) spanning trees, then proving that \[\{1,2,\dots,\exp(cn\log n)\}\subseteq \mathcal{T}_n\] would be equivalent to the uniform bound \[\alpha'(t)\le (1/c+o(1))\frac{\log t}{\log\log t}\] throughout that range. Sedláček initiated the study of this dual problem, and it has since been investigated by Nebeský, Azarija–Škrekovski, Stong, and Chan–Kontorovich–Pak [3], [8], [9], [12], [13]. We do not address this stronger interval/dual problem here.

1.2 Overview of the proof↩︎

The proof is short, and the details are given in the next few sections. Here, we isolate the main ideas and compare them with previous approaches.

A central point of departure, compared to previous works, is that we do not try to construct graphs whose spanning-tree counts are directly distinguishable. Instead, for each word \[\boldsymbol{w}=(w_1,\dots,w_m)\in\{2,\dots,q+1\}^m\] we construct a simple graph \(G_{\boldsymbol{w}}\) such that \(\tau(G_{\boldsymbol{w}})\) is divisible by \[D_{\boldsymbol{w}} = K_m(w_1,\dots,w_m)K_{m-1}(w_1,\dots,w_{m-1}),\] where \(K_r\) is a continuant determinant. Using the continued fraction algorithm, the two factors in \(D_{\boldsymbol{w}}\), taken as an ordered pair, recover the word \(\boldsymbol{w}\). Thus, by the standard divisor-function bound, the divisors \(D_{\boldsymbol{w}}\) themselves take many different values. A second divisor-function bound then shows that these many divisors cannot be supported on too few values of \(\tau(G_{\boldsymbol{w}})\). This kind of argument is familiar in elementary multiplicative number theory. A basic example is the multiplication-table problem: one asks how many distinct products \(ab\) arise from a given set of pairs, and a first lower bound is obtained by controlling how many pairs can produce the same product. Divisor bounds provide the basic multiplicity control; see, for instance, Ford’s work on the multiplication-table problem [14]. In our setting, the role of the products \(ab\) is played by the continuant products \(D_{\boldsymbol{w}}\). The reconstruction lemma (2) shows that, once an ordered factorization \[D_{\boldsymbol{w}} = K_m(w_1,\dots,w_m)K_{m-1}(w_1,\dots,w_{m-1})\] is fixed, the word \(\boldsymbol{w}\) is fixed. Thus the only remaining multiplicity comes from the number of possible factorizations of \(D_{\boldsymbol{w}}\), which is controlled by the divisor function. The novelty is to create such a large supply of distinguishable divisors inside spanning-tree counts by manufacturing them as factors of Matrix–Tree cofactors.

We now briefly discuss how the divisors are produced. The guiding object is a rooted multigraph, presented as a warm-up in 3. It consists of two disjoint paths, on \(m\) and \(m-1\) vertices, together with a distinguished root \(\rho\); each path vertex is joined to \(\rho\) by a prescribed number of parallel edges. Choosing these multiplicities appropriately makes the two path blocks in the reduced Laplacian equal to the tridiagonal matrices defining \[K_m(w_1,\dots,w_m) \qquad\text{and}\qquad K_{m-1}(w_1,\dots,w_{m-1}).\] Thus the warm-up construction realizes the desired product of continuants directly.

The simple-graph construction in 4 is obtained by modifying this multigraph model. The parallel root-edges are replaced by edges to a common set of anchor vertices. This removes multiple edges, but it also couples the path blocks to the anchor block after the root is deleted. To recover a determinant factor, we duplicate each path. The graph then has an involution exchanging the two copies of that path. Passing to the symmetric and antisymmetric subspaces of such an involution is a standard device in spectral graph theory, see for instance [15], [16]. In the present argument, this symmetry has an arithmetic role: inside the Matrix–Tree cofactor, the antisymmetric coordinates decouple from the anchor block and contribute exactly the desired path determinant. The exact linear-algebraic identity is 4, and the resulting divisibility statement is 2.

It remains to explain where the superexponential growth enters. The constructions of Chan–Kontorovich–Pak and Alon–Bucić–Gishboliner are organized around deletion–contraction data associated with a marked edge, i.e.  \[\bigl(\tau(G-e),\tau(G/e)\bigr),\] and local graph operations which transform this two-entry vector by elementary \(2\times2\) integer matrices. In Chan–Kontorovich–Pak, this matrix calculus is linked to continued fractions and then to Diophantine input related to Zaremba’s conjecture. Our continued-fraction structure arises in a different place. It comes from the continuant recurrence \[K_r=w_rK_{r-1}-K_{r-2}, \qquad\text{equivalently}\qquad \binom{K_r}{K_{r-1}} = \begin{pmatrix} w_r&-1\\ 1&0 \end{pmatrix} \binom{K_{r-1}}{K_{r-2}}.\] Thus the common feature is a two-dimensional matrix recurrence, but the quantities being propagated are different; in [9], [10] they are deletion–contraction counts of marked graphs, while here they are consecutive minors of a tridiagonal block inside a Matrix–Tree cofactor.

This difference is also responsible for the larger scale of the construction. In the deletion–contraction framework of the previous constructions, the graph operations are local, and increasing the number of choices available at a given step requires a larger local gadget at that step. Thus the amount of information encoded grows linearly with the number of vertices, leading naturally to exponentially many possibilities. Our construction avoids this local cost by sharing the large part of the alphabet. We introduce \(q\) anchor vertices once, and then each of the \(m\) path positions may choose any one of \(q\) possible weights \(w_i\in\{2,\dots,q+1\}\). Thus the same anchor set supports \(q\) choices at each of \(m\) positions. Taking \(q = \lfloor \varepsilon m \rfloor\), this produces \[q^m=\exp((1+o(1))m\log m)\] candidate continuant divisors while using only \[4m+q-1=(4+\varepsilon)m +O(1)\] vertices.

Finally, the result is related in spirit to Shitov’s recent theorem on \(0\)-\(1\) determinants [11]. Shitov’s construction first realizes the required range using determinants of auxiliary integer-valued matrices, and then uses determinant-preserving gadgets to convert these matrices into \(0\)-\(1\) matrices. In the Matrix–Tree setting, the available determinants are far more constrained, since they must arise as Laplacian cofactors of simple graphs, with the symmetry, sign pattern, and sparsity imposed by graph structure. We therefore do not try to encode the determinant value itself. Instead, we only try to construct many determinant factors inside such cofactors, and then use divisor-counting to force many distinct values of \(\tau\).

1.3 Acknowledgments↩︎

We thank Swee Hong Chan for his beautiful talk at the 10th Lake Michigan Workshop on Combinatorics which introduced us to the problem. We also thank Marcus Michelen, Huy Tuan Pham, Mehtaab Sawhney, and the participants of Desert Discrete Math Workshop 3 for useful discussions. ChatGPT 5.5 Pro drew our attention to the “twin trick” in spectral graph theory and assisted in preparing the manuscript. The author is partially supported by NSF grant DMS-2237646.

2 Preliminaries↩︎

We first recall two standard facts that will be used repeatedly.

We now turn to the continuants used in the construction. For \(r \in \mathbb{Z}_{\geq 0}\) and \(x_1,\dots, x_r \in \mathbb{Z}\), define \(K_r(x_1,\dots, x_r)\) recursively by \[K_0=1,\qquad K_1(x_1)=x_1,\] and, for \(i\ge2\), \[\label{eq:continuant} K_i(x_1,\dots,x_i)=x_i K_{i-1}(x_1,\dots,x_{i-1})-K_{i-2}(x_1,\dots,x_{i-2}).\tag{1}\] Equivalently, \[K_r(x_1,\dots,x_r)=\det T_r(x_1,\dots,x_r),\] where \[T_r(x_1,\dots,x_r)= \begin{pmatrix} x_1&-1&0&\cdots&0\\ -1&x_2&-1&\ddots&\vdots\\ 0&-1&x_3&\ddots&0\\ \vdots&\ddots&\ddots&\ddots&-1\\ 0&\cdots&0&-1&x_r \end{pmatrix}.\]

The next lemma, which is classical, records the continued-fraction interpretation of continuants and the resulting reconstruction algorithm. Due to our sign convention, we will work with negative continued fractions. Recall that for \(r\geq 1\) and integers \(x_1,\dots, x_r\), the (finite) minus continued fraction \([x_r,\dots, x_1]_-\) is defined recursively by \[[x_1]_-:=x_1,\qquad [x_i,\dots,x_1]_-:=x_i-\frac{1}{[x_{i-1},\dots,x_1]_-} \quad (i\ge2).\]

The following crude estimates on the continuants will suffice for our purpose.

The next identity is the linear-algebraic form of the twin-copy idea: from two identical copies, one copy factors out while the other remains coupled to the exterior.

3 Warm-up: a multigraph construction↩︎

As a warm-up, we begin by describing a multigraph version of our construction, which already contains most of the key ideas. In the next section, two modifications will turn this idea into a simple-graph construction. Our multigraphs will be parametrized by \[\boldsymbol{w}=(w_1,\dots,w_m)\in\left\{2,3,\dots,q+1\right\}^m,\] where \(m\geq 3\) is half the number of vertices and \(q\geq 1\) is a free parameter. In our application, we will take \(q = \lfloor \varepsilon m \rfloor\) for sufficiently small \(\varepsilon> 0\).

Throughout, let \(P_r\) denote the path \[1-2-\cdots-r\] on vertex set \([r]\). For \(i\in[r]\), write \[\delta_i^{(r)}:=\deg_{P_r}(i) =\mathbf{1}_{i>1}+\mathbf{1}_{i<r}.\] We now construct \(H_{\boldsymbol{w}}\); see 1. Let \(\rho\) be a distinguished root vertex, and take two paths, disjoint from each other and from \(\rho\), \[u_1-\cdots-u_m, \qquad u'_1-\cdots-u'_{m-1}.\] For \(1\le i\le m\), add \(w_i-\delta_i^{(m)}\) parallel edges between \(u_i\) and \(\rho\). For \(1\le i\le m-1\), add \(w_i-\delta_i^{(m-1)}\) parallel edges between \(u'_i\) and \(\rho\). These multiplicities are nonnegative since \(w_i\ge2\) and \(\delta_i^{(r)}\le2\). Moreover, each endpoint receives at least one edge to \(\rho\), so both paths are attached to the root and the resulting multigraph is connected.

4 The simple graph family↩︎

We now turn the multigraph construction into a simple graph construction. There are two changes. First, the parallel edges from a path vertex to the root \(\rho\) are replaced by edges to distinct “anchor” vertices \(a_1,\dots,a_q\), each of which is adjacent to \(\rho\). Second, for each of the two paths, we create a “twin copy”. The reason for this is the following. In the multigraph construction, deleting the root \(\rho\) left the path blocks completely decoupled. However, in our simple graph construction, the path blocks are still coupled after deleting \(\rho\) due to the anchor vertices, so that the determinant of the path block need not divide the determinant of the cofactor. However, as we saw in 4, two identical path blocks with identical anchor connections have a special block form, and this block form lets us factor off one copy of the path determinant exactly.

We now proceed to the formal details. As before, fix integers \(m\ge3\) and \(q\ge1\), and let \[\boldsymbol{w}=(w_1,\dots,w_m)\in\left\{2,3,\dots,q+1\right\}^m.\] We will construct a simple connected graph \[G_{\boldsymbol{w}}=G_{m,q,\boldsymbol{w}}\] on \[N = N_{m,q} = 4m + q-1\] vertices; see 2. Begin with an anchor star: a root vertex \(\rho\), vertices \(a_1,\dots,a_q\), and edges \(\rho a_t\) for \(1\le t\le q\). Next take four paths, all disjoint from the anchor star: \[u_1-\cdots-u_m, \qquad v_1-\cdots-v_m,\] and \[u'_1-\cdots-u'_{m-1}, \qquad v'_1-\cdots-v'_{m-1}.\] For \(1\le i\le m\), set \[h_i=w_i-\delta_i^{(m)}.\] Join both \(u_i\) and \(v_i\) to the anchor vertices \[a_1,\dots,a_{h_i},\] with the convention that this segment is empty if \(h_i=0\). Similarly, for \(1\le i\le m-1\), set \[h'_i=w_i-\delta_i^{(m-1)},\] and join both \(u'_i\) and \(v'_i\) to \[a_1,\dots,a_{h'_i},\] again with the same convention if \(h_i' = 0\). There are no other edges.

By construction, the graph is simple. Moreover, for each path endpoint \(\delta_i^{(r)}=1\), so \(h_i\ge1\) and \(h'_i\ge1\). Thus every path is attached to the anchor star, and the graph is connected.

The simple graph constructed above has \[N_{m,q}=4m+q-1\] vertices. In the final argument \(q\) will be tied to \(m\), namely \(q=\lfloor \varepsilon m\rfloor\), so these graphs do not realize every integer value of \(n\). However, this can be fixed by a simple padding argument. If \(n\ge N_{m,q}\), let \(G_{\boldsymbol{w}}^{(n)}\) be obtained from \(G_{\boldsymbol{w}}\) by adding \[\ell=n-N_{m,q}\] new vertices \(z_1,\dots,z_\ell\), each adjacent only to the fixed anchor vertex \(a_1\). This padding does not change the number of spanning trees. Indeed, each edge \(a_1z_j\) is a bridge and hence belongs to every spanning tree; deleting all leaves \(z_1,\dots, z_\ell\) and their forced edges gives a spanning tree of \(G_{\boldsymbol{w}}\), and conversely every spanning tree of \(G_{\boldsymbol{w}}\) extends uniquely by adding these edges. Therefore \[\label{eq:padding-preserves-tau} \tau(G_{\boldsymbol{w}}^{(n)})=\tau(G_{\boldsymbol{w}}).\tag{3}\]

4.1 The determinant factor↩︎

In the multigraph construction, deleting the root \(\rho\) left two decoupled path blocks, and hence gave the exact identity (see 1) \[\tau(H_{\boldsymbol{w}}) = K_m(w_1,\dots,w_m)K_{m-1}(w_1,\dots,w_{m-1}).\] For the simple graph \(G_{\boldsymbol{w}}\), the corresponding equality is no longer true: after deleting \(\rho\), the anchor vertices \(a_1,\dots,a_q\) remain, so the path blocks are still coupled to the rest of the cofactor. The point of the twin copies is that the same continuant product nevertheless survives as an exact divisor of the number of spanning trees.

5 Proof of 1↩︎

We now complete the proof by counting. For convenience of notation, for \(m\geq 3\) and \(q\geq 1\), let \[\mathcal{W}_{m,q} := \{2,\dots, q+1\}^m.\] The determinant factorization (2) assigns to each \(\boldsymbol{w} \in \mathcal{W}_{m,q}\) a divisor \[D_{\boldsymbol{w}} := K_m(w_1,\dots, w_m)K_{m-1}(w_1,\dots, w_{m-1})\mid \tau(G_{\boldsymbol{w}}).\] We first use the injectivity of the continuant pair map (2) and the divisor bound to show that the integers \(D_{\boldsymbol{w}}\) take many distinct values, and then use the divisor bound once more to show that these many divisors cannot be supported on too few spanning-tree counts.

We now take \(q=\lfloor \varepsilon m\rfloor\), with \(0<\varepsilon<1\) fixed. Then \(N=4m+q-1=(4+\varepsilon)m+O(1)\), and \[\log q,\;\log(q+1),\;\log N=\log m+O_\varepsilon(1).\] Thus 3 gives, for every fixed \(\eta>0\) and all sufficiently large \(m\), \[\label{eq:asymptotic-m} \log\left|\left\{\tau(G_{\boldsymbol{w}}):\boldsymbol{w}\in\mathcal{W}_{m,q}\right\}\right| \ge \left(1-(6+\varepsilon)\eta\right)m\log m-O_{\varepsilon,\eta}(m).\tag{8}\]

Finally, we finish the proof of the main theorem.

References↩︎