In mathoverflow posting 43081, the question was raised of bounding the number of spanning trees of a graph in terms of $m, n$, the number of edges and vertices. I am interested in the case when $m$ is small compared to $n$ (say $m = c n$ for $c \rightarrow 1$.). In this case, the best bound I have been able to find is the obvious bound $$ \kappa \leq \binom{m}{n-1} $$

There are a lot of papers describing tighter bounds when $m$ is large, such as the bound $\kappa < (2 m/n)^{n-1}$. But are there are any better bounds available in the regime when $m$ is small?

Thanks for any pointers!


Two bounds I found in my old files:

Grimmett, Disc Math 16 (1976) 323-324. Two bounds: $$ \frac{1}{n}\left( \frac{2m}{n-1} \right)^{n-1}.$$ $$ \left( \frac{2m-d}{n-1} \right)^{n-1},$$ where $d$ is the maximum degree. This second one is exact for $K_{1,n-1}$.

Grone and Merris, Disc Math 69 (1988) 97-99. $$ \left( \frac{n}{n-1} \right)^{n-1} \frac{\prod d_i}{\sum d_i},$$ where $d_i$ are the degrees.

In this 1981 paper of mine: http://cs.anu.edu.au/~bdm/papers/Subgraphs1981.pdf , I found the average number of spanning trees within a constant, for random graphs with bounded specified degrees. It is a fun formula as it has both the arithmetic and geometric means of the degrees mixed together (p221). This doesn't give the maximum number of spanning trees, but one can ask if the maximum can be exponentially more than the average, which is not the case for regular graphs.


Yes. See this paper:


(Carsten Thomassen, spanning trees and orientations in graphs; google shows you the full text...), and references therein (esp. McKay's paper [9, op cit])

He treats cubic graphs, which is about as sparse as you can get, but I am sure some of the techniques extend to at least the $k$-regular case.

  • 2
    $\begingroup$ McKay's paper is "B. McKay, Spanning trees in regular graphs, European Journal of Combinatorics 4 (1983) 149–160." $\endgroup$
    – j.c.
    Aug 30 '11 at 19:41
  • 2
    $\begingroup$ Available at cs.anu.edu.au/~bdm/papers/SpanningTrees1983.pdf . Incidentally Fan Chung proved the conjecture which is stated just before the Acknowledgements, but there is an error in the precise upper bound she proved. I don't know if it is resolved yet. Her paper is here: combinatorics.org/Volume_6/Abstracts/v6i1r12.html . $\endgroup$ Aug 30 '11 at 22:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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