Teschner's Bondage-Number Conjecture

Teschner conjectured that every finite simple graph $G$ with at least one edge satisfies $b(G) \leq \frac{3}{2}\Delta(G)$ , where $b(G)$ is the bondage number and $\Delta(G)$ is the maximum degree. Yavari gives a connected cubic bipartite graph on 18 vertices with $b(G)=5$ . Since $\Delta(G)=3$ , this gives $b(G)=5 > \frac{3}{2}\Delta(G)=\frac{9}{2}$ , providing a counterexample and disproving the conjecture.

Result: Disproved(see note)
Status: Resolved
AI contribution: AI-discovered
Method: Construction
Field: Graph theory — domination theory
Posed by: Ulrich Teschner
Year posed: 1995
Years open: 31y
Solved: 2026-08-10
Model: GPT-5.6 Sol Max
Vendor: OpenAI
Collaborators: Yousof Yavari
Verification: Site-confirmed
Publication: Preprint
Significance: 15 / 100
Disclosed cost: —
Wikipedia: Not counted (article postdates the solution)

What was actually shown

Teschner's universal bound b(G) <= (3/2)Delta(G) is false: the 18-vertex cubic bipartite graph has b(G) = 5 against a bound of 4.5. What survives is the restricted statement Teschner actually proved, that the bound holds for graphs of domination number at most three, and Gagarin and Zverovich's 2013 result that it holds for almost all graphs. The counterexample does not suggest a replacement bound, and the correct general upper bound for b(G) in terms of Delta(G) remains open.

What the AI did

According to the author's disclosure and the publicly shared ChatGPT transcript, GPT-5.6 Sol Max was prompted to solve Teschner's conjecture and found an explicit counterexample. The resulting manuscript gives an 18-vertex connected cubic bipartite graph with bondage number 5, together with an exact finite certificate establishing the claimed bondage number. Yavari subsequently checked and wrote up the result.

Verification

Reproduced in full by this site on 13 August 2026. The counterexample is a single 18-vertex graph, so the claim is finite and was checked exhaustively rather than sampled. The edge list was transcribed from equation (3.1) of the preprint and every quantity recomputed independently, without reading or running the author's own verifier. Confirmed: the graph is connected, cubic and bipartite with the stated parts, on 18 vertices and 27 distinct edges, so Delta(G) = 3; its domination number is 6 by exhaustive search over vertex subsets in increasing size; and it has exactly 297 minimum dominating sets, which is the count the paper states, arrived at here independently. For the lower bound, all 20,853 edge subsets of size at most four (27 + 351 + 2925 + 17,550) were tested by the bundle criterion, and every single one leaves at least one minimum dominating set intact, so b(G) >= 5. For the upper bound, deleting the five edges 0-6, 0-10, 0-16, 1-8 and 1-11 raises the domination number to 7, and that was recomputed from scratch on the reduced graph rather than inferred from the criterion, so b(G) <= 5. Therefore b(G) = 5 > 4.5 = (3/2)Delta(G) and Teschner's conjecture is false. The lower-bound enumeration is the entire mathematical content of the claim, so this constitutes a complete independent check. Caveats that remain: the preprint is two days old, is hosted on figshare rather than arXiv, and has no peer review; the author's acknowledgements name Eric Hou (UBC) as an independent verifier, but that is a private check recorded in the paper, not a public endorsement by a domination-theory specialist.

Sources

Submitted by HiddenHawk615 on 13 Aug 2026

Teschner's Bondage-Number Conjecture

What was actually shown

What the AI did

Verification

Sources

Discussion