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.

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.