Cover
Every unguarded point must touch at least one guard. That is ordinary domination.
Exact theorem · Connected P₅-free graphs
A 4/3 lower bound
for secure domination.
Secure guards must answer attacks without leaving the network exposed. This certified 12-vertex graph proves that the best universal multiplier is at least 4/3; a companion all-orders theorem now proves it is exactly 4/3.
γs(G)= 4>α(G)= 3
γs is the fewest secure guards; α is the largest set of points with no links between them.
The problem
What does it mean to guard a network securely?
Respond
If any unguarded point is attacked, an adjacent guard moves there.
Stay covered
After the move, every point must still touch a guard. That extra condition is security.
Interactive proof sketch
Flip the icosahedron. Test the guards.
01 · Start with the icosahedron
- Vertices
- 12
- Edges
- 30
- Symmetries
- 120
Exhaustive certificate
Every small possibility was checked.
The claim does not rest on a picture. A simple independent verifier checks every relevant set of vertices and records why each three-guard set fails.
Open the machine-readable certificate ↗792five-vertex subsetszero induced P₅s
220three-vertex setszero secure triples
495four-vertex sets435 are secure
5triple orbitsunder 120 symmetries
How it was found
The failed ideas mattered.
- 01
Small graphs agreed
Every eligible graph with up to 10 vertices obeyed γs ≤ α, so the stronger statement looked plausible.
- 02
False shortcuts broke
Maximum independent sets, dominating paths, and a tempting dominating-edge lemma all failed as general proof routes.
- 03
SAT searched what remained
The search required α = 3, no induced P₅, connectivity, and failure of every triple—without enumerating every graph.
- 04
Symmetry revealed the object
The 12-vertex model was recognized as the complement of an icosahedron, then independently verified without the SAT clauses.
The status, precisely
The counterexample and sharp coefficient are proved.
The 12-vertex witness
This exact graph has α = 3 and γs = 4. That is a theorem established by exhaustive verification, not a conjecture. The published 3α/2 theorem still holds: 4 ≤ 4.5.
Smallest possible order
Searches exclude smaller examples, but this repository does not include a checkable SAT proof trace. Minimum order is therefore not claimed as a theorem here.
The optimal coefficient
A companion all-orders proof gives γs ≤ α + 1 ≤ 4α/3 for α ≥ 3. This witness attains 4/3, so the coefficient is exact.
The sequel
The former gap closes at 4/3.
The counterexample ruled out coefficient 1 without contradicting the published 3/2 theorem. The continuation proves the matching upper bound for every connected induced-P₅-free graph with α ≥ 3. Walk through the sharp theorem ↗
A second research track
Can tiny chemistry features transfer between proteins?
A corrected FLIP2 experiment suggests they can—but the result is exploratory until tested on an untouched fourth backbone.