On the number of distinct spanning trees in pseudorandom graphs

Abstract

A celebrated result of Otter says the number of distinct unlabelled spanning trees in $K_n$ is ${\alpha }^n$ up to subexponential factors for an absolute constant $\alpha >0$. In this note, we prove that for every $0<\epsilon <\alpha$, there are constants $C$ and $d_0$ such that every $(n,d,\lambda )$-graph with $d\ge d_0$ and $d/\lambda \ge C$ has at least $(\alpha -\epsilon {)}^n$ distinct unlabelled spanning trees.