One tiny graph may overturn a 28-year-old prediction
- What it is
- The paper claims a highly symmetric graph disproves a proposed 1998 bound on network coverage resilience.
- Who did it
- Prateek R. Srivastava
- What it could mean
- Picture a network watched by as few guards as possible. This claimed counterexample breaks a long-standing rule about how many connections must fail before extra guards are needed.
See the check plan
Evidence & validation
From announcement to evidence
Discovery recorded. State of Proof has not yet examined this claim.
Read the original work
The Truncated Octahedral Graph Has Bondage Number Five ↗See the proposed checks
In a separate ephemeral sandbox, source-lock the archive; independently reconstruct the truncated-octahedral graph; verify planarity, cubicity, and domination number 8; enumerate all four-edge deletions with a separately implemented exact checker; then compare results with both supplied verifiers.
No proof docket yet
A docket is the public record of checks and open questions. This paper does not have one yet; the check plan above describes work still to do.
Explore existing proof dockets →
- What it claims
- The paper claims that the planar cubic truncated-octahedral graph has domination number 8 and bondage number 5, giving (5>Delta(T)+1=4) and therefore a counterexample to the stated 1998 planar-graph conjecture. Its finite verification reportedly covers all 58,905 four-edge sets.
- Why this could matter
- One tiny graph may overturn a 28-year-old prediction A 1998 conjecture proposed a limit on how easily coverage can break in certain networks. This paper says a familiar, highly symmetric graph exceeds it. The mathematics can inform coverage models, but practical effects would be indirect.
- If it holds up
- Foundational: researchers must replace the conjectured bound and rethink this corner of graph robustness before drawing broader lessons for coverage or fault-tolerance models.
- If it does not
- The 1998 bound survives this test, and the exhaustive check should reveal whether the graph, deletions, or domination count was encoded incorrectly.
- Impact horizon
- Foundational · Graph theory · Network robustness · Exhaustive verification
- Version
- submitted 2026-09-02 11:48:23 UTC
- Why we tracked it
- a fresh, finite claimed counterexample with source-archived independent C++20 and Python verifiers and a bounded exhaustive replay route; no docket created.
- Highest-risk dependency
- The decisive risk is faithful graph encoding and exhaustive enumeration: a missing or duplicated edge-set branch, or a mistaken domination convention after deletion, could alter the claimed bondage number.
- Available artifacts
- The arXiv record says its TeX source archive contains a complete C++20 verifier and an independently written Python verifier. Those artifacts were not downloaded or executed in this automation.
- Current boundary
- Intake record only; examination not started.