HEXAGONbeta

Counterexamples to Three Conjectures of Ok on Tutte-Polynomial Deletion Ratios

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Jungang Chen ↗

Version 1 / Oct 21, 2026 / CC BY 4.0

Abstract

We disprove Conjectures 7.2.1, 7.2.2, and 7.2.3 from Seongmin Ok's thesis *Aspects of the Tutte Polynomial*. Conjecture 7.2.1 asserts that deleting a non-bridge edge from a connected loopless graph cannot decrease the ratio of acyclic orientations to spanning trees; Conjecture 7.2.2 strengthens this to monotonicity of T_{G-e}(x,2-x)/T_G(x,2-x) on 0 ≤ x ≤ 2. Both fail for an explicit simple planar, 2-connected, chordal 2-tree on 16 vertices, for which deleting one edge multiplies the first ratio by 53/54. A two-parameter construction gives an exact criterion for infinitely many counterexamples. Conjecture 7.2.3, a differential inequality for Tutte-polynomial ratios of matroid minors, fails already for the cycle matroid of the five-edge diamond graph: its asserted nonnegative expression equals -4 at (0,2) and -25/16 at (1/4,7/4). We further construct counterexamples of arbitrarily high vertex connectivity and minimum degree, even when both graphs are chordal, and prove that the sharp supremum of the reverse ratio under one deletion is 2, already within simple planar series-parallel graphs. These counterexamples do not disprove the Merino–Welsh inequalities.

Provenance statement

The research problem was selected by the human contributor. OpenAI ChatGPT (GPT-6) played a substantial role in the mathematical research, including the construction of counterexamples, derivation of exact formulas, development of proofs, computational verification, and preparation of the manuscript. The mathematical arguments are presented as self-contained proofs. AI-generated Python programs using exact integer arithmetic were executed to independently check the main numerical examples and relevant Tutte-polynomial evaluations. These computational checks do not constitute formal proof verification or independent human mathematical review. The manuscript is primarily AI-generated, and no complete independent human verification of its mathematical arguments is claimed. The submitting contributor takes responsibility for the submission and its accurate disclosure of AI involvement.

Tools used

OpenAI
ChatGPTVersion 6 Pro

References

  1. Seongmin Ok, Aspects of the Tutte polynomial , Ph.D. thesis, Technical University of Denmark, DTU Compute PHD-2015, no. 384, written 2015, publication record 2016. Chapter 7, especially Conjectures 7.2.1--7.2.3, printed pp. 92--94. https://backend.orbit.dtu.dk/ws/portalfiles/portal/123426012/phd384_Ok_S.pdflink

Version history

  1. v1 · 6 pagesSubmitted by Jungang ChenInitial depositCurrentOct 21, 2026