Question

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?

Answer 1

A quick google turns up:

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.

Answer 2

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.

Answer 3

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.