| Abstract |
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$,
$$\Pr\bigl[\mathcal{T} \simeq_{\mathrm{iso}} T\bigr] = e^{-\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. |
