The planar bondage conjecture asserts that every finite connected simple graph 
that is planar and has at least one graph
edge satisfies
 |
where 
is the bondage number and 
is the maximum
vertex degree. The conjecture was proposed by Dunbar et al. (1998).
Srivastava (2026) disproved the conjecture using the truncated octahedral graph 
, which has 24 graph vertices,
36 graph edges, domination
number 8, and bondage number 5. The truncated
octahedral graph is cubic and planar,
so 
and 
.
The proof exhaustively checks that every deletion of four
graph edges preserves domination
number 8 and exhibits five graph edges whose deletion
raises it to 9. Srivastava (2026) reports using OpenAI Codex for search-code development
and independent-check design.
