Let $A_n$ $(n \geq 1)$ be the set of all integers $x$ such that there exists a connected graph on $n$ vertices with precisely $x$ spanning trees. It was shown by Sedláček that $|A_n|$ grows faster than the linear function. In this paper, we show that $|A_{n}|$ grows faster than $\sqrt {n} {\rm e}^{({2\pi }/{\sqrt 3})\sqrt {n/\log {n}}}$ by making use of some asymptotic results for prime partitions. The result settles a question posed in J. Sedláček, On the number of spanning trees of finite graphs, Čas. Pěst. Mat., 94 (1969), 217–221.
Let α(n) be the least number k for which there exists a simple graph with k vertices having precisely n ≥ 3 spanning trees. Similarly, define β(n) as the least number k for which there exists a simple graph with k edges having precisely n ≥ 3 spanning trees. As an n-cycle has exactly n spanning trees, it follows that α(n), β(n) ≤ n. In this paper, we show that α(n) ≤ 1⁄3 (n + 4) and β(n) ≤ 1⁄3 (n + 7) if and only if n /∈ {3, 4, 5, 6, 7, 9, 10, 13, 18, 22}, which is a subset of Euler’s idoneal numbers. Moreover, if n 6≡ 2 (mod 3) and n ≠ 25 we show that α(n) ≤ 1⁄4 (n + 9) and β(n) ≤ 1⁄4 (n + 13). This improves some previously estabilished bounds.