Merino–Welsh conjecture for graphs
Merino–Welsh conjecture for graphs
Let be a connected graph without loops or bridges. Write for the number of spanning trees of , for the number of acyclic orientations of , and for the number of totally cyclic orientations of .
Merino–Welsh conjecture. The inequality
should hold.
The three quantities are evaluations of the Tutte polynomial: , , and . The conjecture is known for several graph classes, including sparse or dense graphs, but is not resolved for all connected graphs without loops and bridges.
Sources & referencesView supporting material
Primary source
Luis Ferroni and Benjamin Schröter, “The Merino–Welsh conjecture for split matroids”, arXiv:2204.07132 (2022).
Additional references
2 papers in this index state this conjecture (2010–2022). The statement above is taken from the most recent of them; the others are arXiv:1004.2639.
Source: https://arxiv.org/abs/2204.07132 Merino and Welsh (1999), original conjecture (cited in the source as Conjecture 7.1)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.