# Lower bound on # spanning trees in a connected graph

Are there are any good lower bounds for the number of spanning trees for a connected graph $G$ in terms of (for example) number of edges $E$ or number of vertices $V$ ?

Are improved bounds available if one knows the number of bridges of the graph? (A bridge, aka a cut-edge, is an edge whose removal disconnects the graph)

EDIT:

Here is a simpler statement of the question. What is the minimum number of spanning trees possible for a graph with $m$ edges and $n$ vertices which is (1) 1-edge-connected or (2) 2-edge-connected?

-
Perhaps a bound can be derived by analyzing the Laplacian? The product of the nonzero eigenvalues of the Laplacian is $n$ times the number of spanning trees. –  Joseph O'Rourke Jun 6 '11 at 16:12
Maybe you can look at this other question and answers : mathoverflow.net/questions/43081/… –  BS. Jun 6 '11 at 16:16
This other mathoverflow question was all about upper bounds. I need lower bounds. –  David Harris Jun 6 '11 at 16:42
A simple lower bound is given by the number of minimum spanning trees of the graph, and this number is computable in polynomial time---see e.g., citeseerx.ist.psu.edu/viewdoc/… –  Suvrit Jun 6 '11 at 17:29
I am not interested in computing this quantity for a particular graph. I need lower bounds that apply across the collection of all graphs. (Or perhaps graphs of a particular form, if that is easier to obtain) –  David Harris Jun 6 '11 at 18:18

Undirected simple connected graphs with minimum number of spanning trees by Zbigniew R. Bogdanowicz. According to this paper, the optimal graph is built as follows: Start with the complete graph $K_{n-k}$. Take $k-1$ additional vertices and join them each to the complete graph by a single edge each. Finally, take one more vertex and join it to $m - \left( \binom{n-k}{2} + k-1 \right)$ of the vertices in the complete graph. (So we get $m$ edges total.) One should choose the parameter $k$ to be as small as possible, compatible with the requirement that $m - \left( \binom{n-k}{2} + k-1 \right)$ must be nonnegative.

I couldn't find any references on the $2$-connected version of this.

-
The complete graph has remarkably few spanning trees for the difference between the edges and vertices. I'd guess the $2$-connected version attaches a single cycle instead of a forest to the complete graph. Whether that is optimal or not, it will have relatively few spanning trees. –  Douglas Zare Jun 6 '11 at 22:08

I don't now if this is trivial or not but given a connected graph $G=(V,E)$, there are are at least $|E|-|V|+2$ spanning trees.

Take any spanning tree T. There are $|E|-|V|+1$ edges $e$ that are not in this spanning tree. For any such $e$, $T+e$ has exactly one cycle. There exists an edge $f \in T$ s.t. by removing $f$ the cycle is broken and the tree is still connected. Each $T+e-f$ spanning tree is distinct as they include a different edge $e$.

I also would like to add something implicit to David's answer (but apparently I do not have reputation for commenting). The graph $G$ constructed that way includes the $K_{n-k}$ clique as a subgraph. By Cayley's Theorem, that clique has ${(n-k)}^{n-k}$ spanning trees and therefore $G$ has at least ${(n-k)}^{n-k}$ spanning trees.

-

I was going to guess something like what David found. But a reference certainly trumps a guess. Here is some heuristic reasoning. A connected graph of course has one spanning tree. You asked about using $V$ or $E.$ Let $m(V,E)$ be the number you want and $m_2(V,E)$ the same thing with a requirement to be 2-connected.. If you only know one one them then you can't say anything more. Any time you have a bridge you can contract it to get a graph with one less edge and one less vertex. This suggests looking at $m(V,V-1+k).$ Clearly $m(V,V-1)=1.$ Using a 3-cycle with a tail, $m(V,V)=3$ while $m_2(V,V)=V.$ using $K_4$ with a tail gives 6 spanning trees for $m(V,V+1)$ which beats $9$ for two linked triangles. For $m_2(V,V+1)$ we are facing a $V$-cycle with a cord. This gives $V+s(V-s)$ spanning trees where the smaller cycle cut off by the cord has $s+1 \ge 3$ edges. So best is to take $s=2$, a triangle along with a path joining two vertices. This certainly suggests concentrating as many edges as possible on a few points.

It might be possible to describe various moves which preserve or reduce the number of spanning trees and thus characterize the minimal graphs.

-