11
$\begingroup$

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?

$\endgroup$
7
  • $\begingroup$ 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. $\endgroup$ Jun 6, 2011 at 16:12
  • $\begingroup$ Maybe you can look at this other question and answers : mathoverflow.net/questions/43081/… $\endgroup$
    – BS.
    Jun 6, 2011 at 16:16
  • $\begingroup$ This other mathoverflow question was all about upper bounds. I need lower bounds. $\endgroup$ Jun 6, 2011 at 16:42
  • $\begingroup$ 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/… $\endgroup$
    – Suvrit
    Jun 6, 2011 at 17:29
  • $\begingroup$ 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) $\endgroup$ Jun 6, 2011 at 18:18

3 Answers 3

10
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$ Jun 6, 2011 at 22:08
3
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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