Spanning trees and orientations of graphs
Carsten Thomassen · Journal of Combinatorics · 2010
A conjecture of Merino and Welsh says that the number of spanning trees τ (G) of a loopless and bridgeless multigraph G is always less than or equal to either the number a(G) of acyclic orientations, or the number c(G) of totally cyclic orientations, that is, orientations in which every edge is in a directed cycle.We prove that τ (G) ≤ c(G) if G has at least 4n edges, and that τ (G) ≤ a(G) if G has at most 16n/15 edges.We also prove that τ (G) ≤ a(G) for all multigraphs of maximum degree at most 3 and consequently τ (G) ≤ c(G) for any planar triangulation.