This problem in some ways related to this post.

Let $A_n$ be the set of all integers $x$ such that there exist a connected simple graph of order $n$ having precisely $x$ spanning trees. Study the growth rate of $|A_n|.$

The question was raised by J.Sedlacek in his paper entitled: *On the number of spanning trees of finite graphs, Cas. Pro. Pest Mat., Vol. 94 (1969) 217-221.*

Sedlacek was able to show that $|A_n| = \omega(n)$ and remarked that it is not known if $|A_n| = \omega(n^2).$

Following are some observations about $|A_n|.$

Clearly $|A_n| \leq n^{n-2}$ and $|A_n| \leq |A_{n+1}|$

- Playing with prime partitions a bit it is possible to show that

$$ |A_n| = \omega(\sqrt{n}e^{\frac{2\pi}{\sqrt{3}}\sqrt{n/\log{n}}}) $$

- The following table can be computed using sage+nauty:

$$\begin{array}{ccc} n & |A_n| & \frac{n^{n-2}}{|A_n|}\\\ 1 & 1 & 1 \\\ 2 & 1 & 1 \\\ 3 & 2 & 1.5 \\\ 4 & 5 & 3.2 \\\ 5 & 16 & 7.8 \\\ 6 & 65 & 19.9\\\ 7 & 386 & 43.5\\\ 8 & 3700 & 70.8 \\\ 9 & 55784 & 85.7\\\ 10 & 1134526 & 88.1 \\\ 11 & 27053464 & 87.1 \\\ 12 & 739026332 & 83.7 \\\ \end{array} $$

The bound mentioned under 2. was obtained using a construction of graphs with cut vertices. Since almost all graphs are blocks it is (in a way) reasonable to ask

Question.Is there a construction (using blocks) that can improve bound 2.?

I believe that this should also be provable:

Conjecture.$|A_n| = \omega(k^n)$ for all $k \in \mathbb{N}.$

In case this turns out to be a hard problem I would at least like to extend table 3. further. I am currently computing $|A_n|$ by generating all connected graphs of order $n$ with at least $n$ edges, computing their spanning trees and count distinct such numbers. One optimization could be derived by using the fact that $A_n \subset A_{n+1}$ but this is just a minor thing. I therefore leave the following question for the end:

Question.How can we compute $|A_n|$ quickly?