Journal of Combinatorics

Volume 4 (2013)

Number 1

A note on spanning trees and totally cyclic orientations of 3-connected graphs

Pages: 95 – 104



Fenggen Lin (College of Mathematics and Computer Science, Fuzhou University, Fuzhou, Fujian, China)


Merino and Welsh conjectured that for a 2-edge connected graph $G$ with no loops, the number of spanning trees of $G$ is always less than or equal to either the number of acyclic orientations of $G$, or the number of totally cyclic orientations of $G$. In this paper, we prove that the Merino-Welsh conjecture holds for a 3-connected simple graph of minimum degree at least 4 and average degree at least 7.02.

2010 Mathematics Subject Classification

05C05, 05C20, 05C31

Full Text (PDF format)