MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).
show/hide this revision's text 4 added 101 characters in body; edited title

Spanning trees of 3-edge-connected $k$-edge-connected graphs

Yasuo Teranishi has a paper "The

What are the best lower bounds available on the number of spanning forests of a graph" proving that trees for a 3-edge-connected $k$-edge-connected graph with $m$ edges and $n$ verticeshas ?

There is a simple argument, based on induction on # spanning forests, that shows there are at least $n (3/2)^{n-1}$ \frac{k+1}{2})^{n-1}$ spanning trees irrespective of the number of edges.

Are there any better bounds available Can this be improved with information on knowledge of the number of edgesas well?I.e. given $n$ vertices,

I am particularly interested in the case when $m$ edges, what is small $(m = \Theta(n))$, and $k$ small (particularly the minimum number of spanning trees?

EDIT: Removed confusing notation about spanning forestscase $k = 3$).

show/hide this revision's text 3 edited title

Spanning forests trees of 3-edge-connected graphs
show/hide this revision's text 2 deleted 1 characters in body

Yasuo Teranishi has a paper "The number of spanning forests of a graph" proving that a 3-edge-connected graph with $t$ connected components and $n$ vertices has at least $(3/2)^{n-t} \binom{n}{t}$ n (3/2)^{n-1}$ spanning foreststrees.

Are there any better bounds available with information on the number of edges as well? I.e. given $n$ vertices, $m$ edges, $t$ components, what is the minimum number of spanning foreststrees?

EDIT: Removed confusing notation about spanning forests.
show/hide this revision's text 1