Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
    
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

3 Answers 3

up vote 7 down vote accepted

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.

share|improve this answer
    
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.

share|improve this answer

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.