The Kirchhoff's theorem is a classical result for counting the number of spanning trees in a graph. 


However, what are the best known upper bounds on the number of spanning trees in a graph in terms of structural parameters (e.g., number of vertices, degrees, etc.) instead of algebraic quantities?



Number of spanning trees: bounds from structural parameters
I had an email discussion with Russell Lyons a few years ago about maximizing the number of spanning trees among all graphs with a given number of vertices and edges. He had a simple argument for an upper bound of $(2e/v)^{v-1}$. There's an even simpler argument for an upper bound of $e\choose v-1$. Russell thought there was a good bound for regular graphs due to McKay. 


As for lower bounds, if the graph is not connected, it has zero spanning trees, and even an $n$-vertex graph with just $n-1$ edges missing (compared to the complete graph) may not be connected. I suppose one could restrict to connected graphs and then ask for a minimum. 


EDIT: Here are bibliographical details on two papers by McKay: 


McKay, Brendan D., Spanning trees in regular graphs, European J. Combin. 4 (1983), no. 2, 149–160, MR 85d:05194.


McKay, Brendan D., Spanning trees in random regular graphs, Proceedings of the Third Caribbean Conference on Combinatorics and Computing (Bridgetown, 1981), pp. 139–143, Univ. West Indies, Cave Hill Campus, Barbados, 1981, MR 83g:05030. 


