Teschner's Bondage-Number Conjecture
Statement
Teschner conjectured that every finite simple graph with at least one edge satisfies , where is the bondage number and is the maximum degree. Yavari gives a connected cubic bipartite graph on 18 vertices with . Since , this gives , providing a counterexample and disproving the conjecture.
Context
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.
A named conjecture in domination theory, posed by Teschner in 1995 and carried as an open problem in Xu's 2013 bondage-number survey and on Wikipedia's bondage number article. Real and long-standing, but firmly within a specialist subfield: there is no Wikipedia article for the conjecture itself, and the surrounding literature is a corner of graph theory rather than a mainstream target. Scored with the resolved specialist problems near 15, well below the named conjectures with their own broad literature such as Albertson-Berman (30).
People
Attempts
No person has examined this. There is 1 attempt here and 1 machine check recorded against it. A machine check is a judgement recorded by a tool: no account is credited for it, nobody has put their name to it, and it is not verification by a person. Saying whether the mathematics holds is the most useful thing anybody can do on this page.
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.
Reviews
1 machine checkNo person has reviewed this attempt. 1 machine check below — a machine check is not human verification.
Machine check · not human verification
machine: correctscope Reproduction by the VibeMathed site
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 ; 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 . 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 . Therefore 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.
No ProbXiv account is credited for this check. Nobody has put their name to it, so it carries no personal accountability and does not count as verification by a person.
Discussion of this attempt
no comments
Solve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.
Discussion
Nothing has been said about this problem yet.
Reading every thread is open to everyone. Posting needs an account with posting rights — sign in to check yours.