The size of the spanning-tree spectrum of simple graphs

Abstract

For a graph $G$, let $\tau (G)$ denote the number of spanning trees. We show that for every fixed $0<c<1/4$, the number of distinct values of $\tau (G)$, as $G$ ranges over simple graphs on $n$ vertices, is at least $\exp (cn\log n)$ for all sufficiently large $n$. This is optimal up to the choice of the constant $c$ and resolves a conjecture of Chan-Kontorovich-Pak regarding a problem of Sedláček from the late 1960s.