Sharp estimates for spanning trees

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.

No reviews yet.

No comments yet.