GPT-5.6 produced an 18-vertex counterexample refuting Teschner's 31-year bondage-number conjecture

2026-08-11

An 18-vertex cubic bipartite graph attributed to GPT-5.6 has bondage number b(G)=5, above (3/2)Δ(G)=4.5, refuting Teschner's 1995 conjecture; the bundled Python verifier reproduces.

What problem this solves

Graph theory has a quantity called the domination number γ(G): the smallest set of vertices such that every vertex is either in the set or next to a member of it. The bondage number b(G) is its fragility twin, the fewest edges whose removal makes the domination number go up. In 1995 Teschner proved that graphs with domination number at most 3 satisfy b(G) ≤ (3/2)Δ(G), where Δ(G) is the maximum degree, and conjectured the bound for all graphs. It held across many graph classes for thirty years. This paper kills it with a counterexample.

Method

The counterexample is an 18-vertex connected cubic (every vertex has degree 3) bipartite graph. The argument has three steps, all hand-checkable or exactly enumerable:

• γ(G)=6. First rule out any 5-vertex dominating set by counting across the bipartition. If a vertices are chosen from side X and 5−a from side Y, the uncovered X-vertices must be covered by the 5−a degree-3 Y-vertices and the uncovered Y-vertices by the a X-vertices, which forces a∈{2,3}. Enumerating the condition that the two chosen vertices have disjoint neighborhoods whose union covers exactly six vertices leaves one vertex undominated in every case. A concrete 6-set D₀={0,1,2,3,14,15} dominates, so γ=6.
• b(G)≤5. Delete the five edges incident to the adjacent vertices 0 and 6; both become isolated, the remaining 16-vertex subgraph has domination number 5, and γ(G−F₅)=7>6.
• b(G)≥5. The only machine-assisted part. Enumerate all C(18,6)=18,564 six-sets, confirm exactly 297 dominate, then test all C(27,4)=17,550 four-edge deletions; each leaves at least one 6-set still dominating, so four edges never suffice.

The load-bearing lemma (Lemma 2.2, the bundle criterion): a dominating set D still dominates after deleting edges F iff, for every vertex x outside D, not all of x's edges into D are removed. The enumeration rests on this.

Re-running the paper's appended Python, plus two extra checks (that no 5-set dominates, and that after F₅ a 7-set dominates but no 6-set does), everything passes. The computational core of the counterexample reproduces.

Results

The single result is the counterexample: b(G)=5, above (3/2)Δ(G)=4.5, so Teschner's conjecture is false. No benchmark table, because this is not a benchmark exercise.

Why it matters

On two levels. Mathematically, a 31-year-old conjecture falls in the smallest possible way: the counterexample lives on cubic graphs (the lowest nontrivial degree), so the 3/2 constant fails even in the tamest class. The AI angle is what the Chinese community is actually discussing. The author's generative-AI disclosure states the counterexample was produced by OpenAI's GPT-5.6 Sol at the max reasoning setting after he posed the problem, then revised, expanded, independently verified, and signed off by the author. That pushes the LLM's role in mathematics one step past doing contest problems (AlphaProof at the IMO) toward constructing counterexamples to open conjectures.

Limitations

• Figshare preprint, not peer-reviewed.
• Only the computational part (γ=6, b≥5, b≤5) is reproducible. The hand argument ruling out 5-sets was not re-derived line by line; it is consistent with the brute-force result that zero 5-sets dominate, which raises confidence.
• The disclosure names GPT-5.6 Sol Max but gives no prompt, settings, or split of how much the model produced unaided versus how much the human added through verification and editing. Credit between model and author cannot be divided from the paper alone.
• Independent verification was done by Eric Hou; the depth of that check is not specified.

Terms

• domination number γ(G): the smallest vertex set such that every vertex is in it or adjacent to a member of it.
• bondage number b(G): the fewest edges whose removal raises the domination number; a measure of how fragile domination is.
• Δ(G) (maximum degree): the largest number of neighbors any vertex has.
• cubic graph: a graph where every vertex has degree 3.
• bipartite graph: a graph whose vertices split into two groups with all edges crossing between them.

Source

• Paper

What people are saying

• GPT-5.6 Solves Two Open Graph Theory Problems Unresolved for Decades No-Performer-2242

All paper explainers