Sharp estimates for spanning trees

Abstract

We prove the following sharp estimate for the number of spanning trees of a graph in terms of its vertex-degrees: a simple graph $G$ on $n$ vertices has at most $(1/n^2){\prod }_{v\in V(G)}(d(v)+1)$ spanning trees. This result is tight (for complete graphs), and improves earlier estimates of Alon from 1990 and Kostochka from 1995 by a factor of about $1/n$ (for dense graphs). We additionally show that an analogous bound holds for the weighted spanning tree enumerator of a (nonnegatively) weighted graph as well.

It has been pointed out to us when this paper was under review that the results are not new; in fact a stronger bound was proved by Grone and Merris [Discrete Math. 69 (1988), 97-99]

References in corpus (2)

• Linear algebraic techniques for weighted spanning tree enumeration
• Alternative proof of upper bound of spanning trees in a graph