Merino-Welsh Conjecture

The Merino-Welsh conjecture (Merino and Welsh 1999) asserts that every connected graph without graph loops or graph bridges satisfies

$max{T_G(2,0),T_G(0,2)}>=T_G(1,1).$

(1)

Here is the Tutte polynomial. The three quantities count graph orientations having no directed cycles, graph orientations in which every edge lies on a directed cycle, and spanning trees, respectively.

The multiplicative Merino-Welsh conjecture (Conde and Merino 2009) is the stronger inequality

(2)

It remains open for graphs. Its direct extension to matroids without loops or coloops was refuted by Beke et al. (2024). A matroid loop belongs to no matroid basis, while a coloop belongs to every matroid basis.

Csikvári (2026) conjectured a sharp universal replacement for matroids. Let be the largest real polynomial root of

(3)

Liu (2026) reported a proof that every finite matroid of this type satisfies

(4)

Known counterexamples for every make the least nonnegative universal parameter. More precisely, if has elements and connected components, then for ,

(5)

Examples in Liu (2026) show that the exponential rate is sharp throughout this interval.

Liu (2026) reports that GPT-6 Astra and Claude Opus 5 assisted with mathematical exploration, proof development, exact computation, and code. As of Sep. 27, 2026, the result had not undergone external peer review, and the rational replacement table used by the proof had not been independently recomputed.

Chen and Xie (2026) gave a separate direct inductive proof of the universal threshold inequality for loopless and coloopless matroids. This is the same threshold already covered by Liu (2026), not a proof of the original multiplicative conjecture for graphs.

For chordal graphs, the original multiplicative inequality has been proved. Xu et al. (2026) showed that every connected bridgeless simple chordal graph satisfies . Xu et al. (2026) report using ChatGPT to explore possible approaches to the proof.

Chen et al. (2026) determined the smallest multiplicative counterexample among parallel thickenings of uniform matroids of matroid rank on elements with . It has 62 elements and is obtained by replacing each element of the rank-21 uniform matroid on 31 elements by two parallel copies. Every -thickening in this family with satisfies the inequality. The 62-element minimum is restricted to this family and is not asserted over all matroids or over graphs.

Explore with Wolfram|Alpha

More things to try:

References

Beke, C.; Csáji, G. K.; Csikvári, P.; and Pituk, S. "The Merino-Welsh Conjecture Is False for Matroids." Adv. Math. 446, Article 109674, 2024. https://doi.org/10.1016/j.aim.2024.109674.Chen, J.; Jin, X.; and Ma, T. "On Minimum-Size Matroid Counterexamples to the Multiplicative Merino-Welsh Inequality." 20 Oct 2026. https://arxiv.org/abs/2610.27706.Chen, J. and Xie, J. "A Sharp Merino-Welsh-Type Inequality for Matroids." 5 Oct 2026. https://arxiv.org/abs/2610.06589.Conde, R. and Merino, C. "Comparing the Number of Acyclic and Totally Cyclic Orientations with That of Spanning Trees of a Graph." Int. J. Math. Combin. 2, 79-89, 2009.Csikvári, P. "Around the Merino-Welsh Conjecture: Improving Jackson's Inequality." Europ. J. Combin. 137, Article 104402, 2026. https://doi.org/10.1016/j.ejc.2026.104402.Liu, M. "The Sharp Threshold for the Multiplicative Merino-Welsh Inequality on Matroids." 23 Sep 2026. https://doi.org/10.5281/zenodo.22911905.Merino, C. and Welsh, D. J. A. "Forests, Colorings and Acyclic Orientations of the Square Lattice." Ann. Combin. 3, 417-429, 1999.Xu, S.; Dong, F.; and Xu, K. "The Multiplicative Merino-Welsh Inequality for Chordal Graphs." 19 Oct 2026. https://arxiv.org/abs/2610.25817.

Cite this as:

Weisstein, Eric W. "Merino-Welsh Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Merino-WelshConjecture.html

Merino-Welsh Conjecture

See also

Explore with Wolfram|Alpha

References

Cite this as:

Subject classifications