KAIST Discrete Math Seminar

One of the most fundamental properties of a connected graph is the existence of a spanning tree. Also the number τ(G) of spanning trees is an important graph invariant. It plays a crucial role in Kirchhoff’s classical theory of electrical networks, for example in computing driving point resistances. More recently, τ(G) is one of the values of the Tutte polynomial which now plays a central role in statistical mechanics. So are a(G), the number of acyclic orientations, and c(G), the number of orientations in which every edge is in a directed cycle. As a first step towards convexity properties of the Tutte polynomial, Merino and Welsh conjectured that

for every loopless and bridgeless multigraph G. We shall here prove that τ(G) ≤ c(G) for all loopless and bridgeless multigraphs with n vertices and at least 4n edges and that τ(G) ≤ a(G) for all loopless multigraphs with n vertices and at most 16n/15 edges. We also verify the conjecture for cubic graphs (which are in between these two bounds).