Number of spanning trees: bounds from structural parameters 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?
 A: 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. 
A: Thank you all for your kind answers. In my question I was specifically interested in bounds given in terms of readily available quantities like number of vertices, edges, max degree, etc. Thanks to Gerry for his references. I have also learn about other references on my own. Essentially there is a good list of bounds in 
L. Feng, et al., Sharp upper bounds for the number of spanning trees of a graph, Appl. Anal. Discrete Math. 2 (2008), 255-259.
A: Kostochka's Upper Bound. It is now almost seven years that no one has mentioned  the following widely-known, proved, completely general upper bound in terms of the degree-sequence:

Theorem (A. Kostochka) . Every finite graph $G$ has $\leq\frac{1}{\lvert G\rvert-1}\prod_{V\in V}\mathrm{d}_G(v)$ spanning trees.

Here, 'graph'='irreflexive symmetric binary relation on a set', and $\mathrm{d}_G(v)=\lvert\{e\in E(G)\colon v\in e\}\rvert$ denotes the vertex-degree. Needless to say, 

this bound is sharp in the sense that there is an infinite family of graphs for which the bound holds with equality: the stars $K^{1,\lvert G\rvert-1}$, which are themselves trees. 

Restricted to the class of all trees, the stars are of course the only graphs for which Kostochka's bound is sharp.
I find it a plausible  


*

*conjecture that stars are the only graphs for which Kostochka's bound is attained, but I do not know whether this is proved. 


A proof of the above theorem of Kostochka was published in 

A. V. Kostochka: The Number of Spanning Trees in Graphs with a Given Degree Sequence Random Structures and Algorithms 6(2-3) 1995

A: kirchhoff's theorem gives both a lower and upper bound
