Multiplicative Merino–Welsh conjecture

Research log for issue #44. The conjecture is open.

Statement and literature

For every connected loopless and bridgeless multigraph, the number of spanning trees squared is at most the product of the numbers of acyclic and totally cyclic orientations.

The recent papers, arXiv citations, and Hexagon postings checked in November 2026 give no resolution for all graphs. The two-element reduction was rediscovered during the opening investigation and is credited to Chen, Jin, and Ma. The argument below gives an additional necessary condition.

Spanning-tree bounds on paired edges

In a minimum-edge counterexample, a uniformly random spanning tree meets each parallel pair with probability strictly between 3/53/5 and 4/54/5. It contains both edges of each series pair with probability strictly between 1/51/5 and 2/52/5. Deleting a parallel pair leaves a bridgeless graph. Dually, contracting a series pair leaves a loopless graph. In particular, no three-edge bond contains a parallel pair, and no triangle contains a series pair.

Proof

Write a(N)=TN(2,0)a(N)=T_N(2,0), c(N)=TN(0,2)c(N)=T_N(0,2), and t(N)=TN(1,1)t(N)=T_N(1,1) for a matroid NN. Let MM be the cycle matroid of a minimum-edge graph counterexample. Its direct-sum factors are graphic, and the three evaluations multiply over direct sums, so MM is connected. The elementary reductions in Chen, Jin, and Ma, §5 apply to MM: each element belongs to one pair, series or parallel. The series-side argument can use M*M^*, because the dual of each proper minor of M*M^* is a proper minor of MM and satisfies the same product inequality whenever it is loopless and coloopless.

Let M1M_1 result from deleting one element of a parallel pair and let ee be the survivor. Set D=M1\eD=M_1\setminus e and C=M1/eC=M_1/e. Parallel deletion preserves connectivity of the matroid. The pair is maximal, so CC is loopless and coloopless. In particular, t(C),a(C),c(C)>0t(C),a(C),c(C)>0. Normalize by putting

q=t(D)t(C),x=a(C)a(D),r=c(D)c(C).q=\frac{t(D)}{t(C)},\qquad x=\frac{a(C)}{a(D)},\qquad r=\frac{c(D)}{c(C)}.

Lemma 5.7 of Chen, Jin, and Ma gives 0<x≤10\lt x\le 1 and 0≤r≤10\le r\le1. Deletion–contraction at ee, followed by the parallel-extension formula, gives the evaluation triples

actM1a(D)+a(C)c(C)(1+r)t(C)(q+1)Ma(D)+a(C)c(C)(3+r)t(C)(q+2).\begin{array}{c|ccc} & a & c & t\\ M_1 & a(D)+a(C) & c(C)(1+r) & t(C)(q+1)\\ M & a(D)+a(C) & c(C)(3+r) & t(C)(q+2). \end{array}

Put s=(q+2)2s=(q+2)^2 and d=3+rd=3+r. Minimality gives the conjectured inequality for M1M_1 and CC. Comparing the normalized ratios ac/t2ac/t^2 of MM to those two minors gives, respectively,

r>2q2+2q−12q+3,(1+x)d<xs.r>\frac{2q^2+2q-1}{2q+3}, \qquad (1+x)d<xs.

The second inequality implies r<s/2−3r<s/2-3 since x≤1x\le1. The difference of this upper bound and the first lower bound equals

(2q−1)(q+2)22(2q+3).\frac{(2q-1)(q+2)^2}{2(2q+3)} .

It must be positive, so q>1/2q>1/2. The first lower bound then exceeds 1/81/8, since its difference from 1/81/8 is (2q−1)(8q+11)8(2q+3)\frac{(2q-1)(8q+11)}{8(2q+3)}. Consequently c(D)>0c(D)>0. Since DD is loopless, this makes it coloopless as well, so minimality also applies to DD.

Comparing ac/t2ac/t^2 of MM to that of DD now gives (1+x)dq2<rs(1+x)dq^2<rs. The prior comparison to CC gives 1+x>s/(s−d)1+x>s/(s-d), because x(s−d)>dx(s-d)>d. Combining the two yields

dq2<r(s−d),3q2<r(4q+1−r)≤4q.dq^2 < r(s-d),\qquad 3q^2 < r(4q+1-r)\le 4q .

For the last inequality, 4q−r(4q+1−r)=(1−r)(4q−r)≥04q-r(4q+1-r)=(1-r)(4q-r)\ge0 since q>1/2q>1/2 and r≤1r\le1. Hence q<4/3q<4/3. The chance of using the parallel pair is 2/(q+2)2/(q+2) by the spanning-tree count, so it lies in (3/5,4/5)(3/5,4/5). Complementing bases in the dual gives the stated series probability and the dual assertion on contracting the pair.

What remains

The bounds constrain weighted spanning-tree marginals after replacing each parallel pair by an edge of weight 22 and suppressing each series pair into an edge of weight 1/21/2 in a cycle-matroid-equivalent representation. A proof that every such compressed graph violates a necessary condition, or a concrete graph with product below its squared tree count, would resolve the full conjecture. The bounds alone give neither conclusion.