Anticoncentration of random spanning trees in almost regular graphs

The celebrated formula of Otter \emph{[Ann. of Math. (2) 49 (1948), 583–599]} asserts that the complete graph contains exponentially many non-isomorphic spanning trees. In this paper, we show that every connected almost regular graph with sufficiently large degree already contains exponentially many non-isomorphic spanning trees. Indeed, we prove a stronger statement: for every fixed $n$-vertex tree $T$, $$\mathrm{Pr}\left[\mathcal{T}{\simeq }_{\mathrm{i}\mathrm{s}\mathrm{o}}T\right]=e^{-\mathrm{\Omega }(n)},$$ where $\mathcal{T}$ is a uniformly random spanning tree of a connected $n$-vertex almost regular graph with sufficiently large degree. To prove this, we introduce a graph-theoretic variant of the classical balls–into–bins model, which may be of independent interest.