{"id":"arxiv/2609.30201","url":"https://arxiv.org/abs/2609.30201","tags":["math.CO"],"score":0,"title":"An extremal theorem for non-isomorphic spanning trees","domain":"math.CO","source":"arxiv","authors":["Zhifei Yan","Lu-Ming Zhang"],"reviews":0,"subject":"math.CO","summary":"For a graph $G$, let $τ_{\\mathrm{iso}}(G)$ denote the number of isomorphism classes of its spanning trees. For every fixed $d\\ge3$ and all sufficiently large $n$, we prove that every connected $n$-vertex graph $G$ with $δ(G)\\ge d$ satisfies \\[τ_{\\mathrm{iso}}(G)\\ge τ_{\\mathrm{iso}}(K_{d,n-d})=A_dn^{d-1}+O_d(n^{d-2}),\\] for an explicit constant $A_d>0$, and $K_{d,n-d}$ is the unique minimizer. This confirms a conjecture of Bitonti, Michel and Scott and extends it to every $d\\ge3$. We also show that any such graph with $O(n^{d-1})$ spanning-tree types has all but a bounded number of vertices…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-24","reactions":{}}