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).

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$). 3 edited title # Spanning foreststrees of 3-edge-connected graphs 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.

1