Non-isomorphic spanning trees count lower bound

Conjecture 4.2 · arXiv:2603.17630

arXiv Conjecture high confidence— first stated 2026-03-18

Authors: Veronica Bitonti, Lukas Michel, Alex Scott

Status open high confidence

Conjecture 4.2 from arXiv:2603.17630 (March 2026) asserts that Ω(n^{d-1}) is the correct lower bound for the number of non-isomorphic spanning trees in connected n-vertex graphs with minimum degree at least d, with K_{d,n-d} as the conjectured extremal example. The same paper establishes the weaker bound n^{Ω(d)} (tight only up to the constant in the exponent), which proves Lee's conjecture in strong form but falls short of the d-1 exponent claimed in Conjecture 4.2. No follow-up paper resolving or making partial progress on this specific conjecture was found in the indexed literature as of May 2026.

Reviewer notes. The conjecture is very recent (March 2026). The source paper itself proves n^{Omega(d)} non-isomorphic spanning trees for graphs of minimum degree d, which is tight only up to the constant in the exponent; Conjecture 4.2 asks for the sharp exponent d-1, achieved by K_{d,n-d}. The predecessor paper arXiv:2601.07740 (Anticoncentration of random spanning trees in almost regular graphs) established a similar result for almost regular graphs and predates the source paper. No follow-up addressing Conjecture 4.2 was found after 5 web calls.

Auto-reviewed 2026-05-14 with claude-sonnet-4-6 (web search enabled).

Conjecture. Let $d$ be sufficiently large, and let $n$ be sufficiently large relative to $d$. Suppose that $G$ is a connected graph with $n$ vertices and minimum degree at least $d$. Then, the number of non-isomorphic spanning trees of $G$ is at least $\Omega(n^{d-1})$.

Context

The anticoncentration property of Conjecture 4.1 would imply only $n^{(1/2-o_n(1))(d-1)}$ non-isomorphic spanning trees, but $K_{d,n-d}$ has $\Omega(n^{d-1})$ non-isomorphic spanning trees. The authors conjecture that this larger quantity gives an essentially optimal lower bound, with $K_{d,n-d}$ being an extremal example.

Source paper

Anticoncentration of random spanning trees in graphs with large minimum degree
Veronica Bitonti, Lukas Michel, Alex Scott · 2026-03-18
https://arxiv.org/abs/2603.17630