Source authenticated

Teschner's Bondage-Number Conjecture

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.

Exact FrontierDelta

Prior state unknown→disproved

Scope and record

Occurred: Aug 10, 2026

Delta type: SOURCE CLAIM

Assumptions: VibeMathed verification: site-confirmed. Publication: preprint. AI contribution: ai-discovered. Imported under CC BY 4.0.

Canonical aliases: Teschner's Bondage-Number Conjecture · Teschner bondage conjecture

Confidence: Not scored

Registry verification: site confirmed · preprint · resolved

Open the source record ↗

Attribution

VibeMathed
registry · event recorded by

Yousof Yavari
human · human collaborator

GPT-5.6 Sol Max
model · ai model contributor · OpenAI

Evidence vector

SourceReplayReproducedFormal proofStatement auditExternal checkExpert reviewPeer review

Named evidence

VibeMathed record: Teschner's Bondage-Number Conjecture

specialist registry · passed

Reproduced in full here 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) and every quantity recomputed independently, without reading or running the author's verifier. Confirmed: connected, cubic and bipartite with the stated parts, 18 vertices and 27 distinct edges, so $\Delta(G) = 3$; domination number 6 by exhaustive search; and exactly 297 minimum dominating sets, the count the paper states, arrived at here independently. For the lower bound, all 20,853 edge subsets of size at most four were tested by the bundle criterion, and every one leaves at least one minimum dominating set intact, so $b(G) \ge 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, recomputed from scratch on the reduced graph rather than inferred from the criterion, so $b(G) \le 5$. Therefore $b(G) = 5 > 4.5 = \frac32\Delta(G)$ and the conjecture is false. That enumeration is the entire mathematical content of the claim, so this is a complete independent check. Caveats: the preprint is two days old, is hosted on figshare rather than arXiv, and has no peer review; the acknowledgements name Eric Hou (UBC) as an independent verifier, but that is a private check, not a public endorsement by a specialist.

Source ↗

ChatGPT conversation in which the counterexample was produced

witness · pending

transcript link supplied by the VibeMathed registry.

Source ↗

Xu, On Bondage Numbers of Graphs: A Survey with Some Comments (2013)

paper · pending

paper link supplied by the VibeMathed registry.

Source ↗

Gagarin and Zverovich, The bondage number of graphs on topological surfaces and Teschner's conjecture (2013)

paper · pending

paper link supplied by the VibeMathed registry.