Merino–Welsh conjecture for graphs

Let GG be a connected graph without loops or bridges. Write τ(G)\tau(G) for the number of spanning trees of GG, b1(G)b1(G) for the number of acyclic orientations of GG, and b1(G)b1^*(G) for the number of totally cyclic orientations of GG.

Merino–Welsh conjecture. The inequality

max(α(G),α(G))τ(G)\max(\alpha(G),\alpha^*(G))\geq\tau(G)

should hold.

The three quantities are evaluations of the Tutte polynomial: τ(G)=TG(1,1)\tau(G)=T_G(1,1), α(G)=TG(2,0)\alpha(G)=T_G(2,0), and α(G)=TG(0,2)\alpha^*(G)=T_G(0,2). 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

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.