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.
- Conde and Merino pose the product inequality. The original maximum inequality is due to Merino and Welsh.
- Noble and Royle, Lemmas 2.2–2.4 and Theorem 4.5 restrict a smallest counterexample to series and parallel classes of size two or three and prove the conjecture for series–parallel graphs.
- Chen, Jin, and Ma, Section 5 improve the class-size restriction to exactly two for matroids. Their reductions stay within graphic matroids because they use minors, components, and the order-dual argument for series classes. Thus the improvement also applies to a smallest graph counterexample.
- Beke et al. disprove the matroid extension. Chen and Xie determine the sharp axis threshold for matroids, which is greater than 2. Chen's permutation-Tutte counterexamples concern the auxiliary inequality of Csikvári, §7.3.
- Váli proves the product inequality for sufficiently sparse or dense graphs. Xu, Dong, and Xu cover bridgeless chordal graphs. Chen and Xie give quantitative inequalities for joins.
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 and . It contains both edges of each series pair with probability strictly between and . 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 , , and for a matroid . Let 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 is connected. The elementary reductions in Chen, Jin, and Ma, §5 apply to : each element belongs to one pair, series or parallel. The series-side argument can use , because the dual of each proper minor of is a proper minor of and satisfies the same product inequality whenever it is loopless and coloopless.
Let result from deleting one element of a parallel pair and let be the survivor. Set and . Parallel deletion preserves connectivity of the matroid. The pair is maximal, so is loopless and coloopless. In particular, . Normalize by putting
Lemma 5.7 of Chen, Jin, and Ma gives and . Deletion–contraction at , followed by the parallel-extension formula, gives the evaluation triples
Put and . Minimality gives the conjectured inequality for and . Comparing the normalized ratios of to those two minors gives, respectively,
The second inequality implies since . The difference of this upper bound and the first lower bound equals
It must be positive, so . The first lower bound then exceeds , since its difference from is . Consequently . Since is loopless, this makes it coloopless as well, so minimality also applies to .
Comparing of to that of now gives . The prior comparison to gives , because . Combining the two yields
For the last inequality, since and . Hence . The chance of using the parallel pair is by the spanning-tree count, so it lies in . 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 and suppressing each series pair into an edge of weight 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.