What are the best lower bounds available on the number of spanning trees for a $k$-edge-connected graph with $m$ edges and $n$ vertices?
There is a simple argument, based on induction on # spanning forests, that shows there are at least $n (\frac{k+1}{2})^{n-1}$ spanning trees irrespective of the number of edges. Can this be improved with knowledge of the number of edges?
I am particularly interested in the case when $m$ is small $(m = \Theta(n))$, and $k$ small (particularly the case $k = 3$).
The problem of determining the minimum number of spanning trees in a connected graph on $n$ vertices and $m$ edges was first asked by Boesch, Satyanarayana and Suffel in Least reliable networks and the reliability domination. It was solved in Undirected simple connected graphs with minimum number of spanning trees by Z.R. Bogdanowicz, showing that the minimum is achieved by a certain graph $L(n,m)$ which is constructed as follows: For fixed $n$ and $n-1\le m\le \binom{n}{2}$ solve the equation $$m=\binom{n-k}{2}+k-1+r$$ for $1\le k\le n-1$ and $1\le r \le n-k$, and form $L(n,m)$ as the union of a $(n-k)$-clique together with a vertex of degree $r$, and $k-1$ vertices of degree 1.
Now, it isn't clear to me from the question if this is what you wanted, or if you are interested in $f(n,m,k)$, the minimum number of spanning trees on graphs with $n$ vertices, $m$ edges that are $k$-edge connected. In this case the methods of the second paper I linked to, should be adaptable to give an answer for small values of $k$. (Notice that for $3$- edge connectivity it is already an optimal bound for $m$ in the range $\binom{n-1}{2}+3\le m\le \binom{n}{2}$.)
Here is a comment on $2$-edge connected graphs. Pick a critical edge $uv$ whose removal leaves the graph $1$-edge connected. There will be another critical edge $u'v'$, minimal with respect to the size of the block containing $u$ and $u'$, it's easy to see that this block will be $2$-edge connected, and that replacing $uv$ with $u'v$ reduces the number of spanning trees. This makes $u'$ a cut vertex, reducing our analysis to a (possibly) smaller graph.
If you use this repeatedly you will obtain that $2$-edge connected graphs with a minimum number of spanning trees are obtained from $3$-edge connected graphs by taking one point unions with cycles or pyramids (graphs isomorphic to a cycle and a central vertex joined to all other vertices). When coming to $3$-edge connected graphs you don't have to worry any more about moving a single edge around since, this will make the graph at worst $2$-edge connected and you can go over the above procedure again. Show that if you have an induced path of length at least three $u\to v\to w\to t$, then switching the edge $uv$ to $vt$ will decrease the number of spanning trees. Note that graphs without induced paths of length $3$ are very similar to the threshold graphs mentioned in the paper and they can be characterized.
From here you conclude that the minimal graphs you are looking for are obtained from complete graphs by adding at most one vertex and taking one point unions with cycles or pyramids.
