Cover
Every unguarded vertex touches a guard. This is ordinary domination.
Solved theorem · connected induced-P₅-free graphs · α ≥ 3
The answer is
exactly 4/3.
How many guards does a network need if every guard must be able to answer an attack without leaving the rest exposed? A published upper bound was 3/2 times a natural graph parameter. The sharp multiplier is smaller: 4/3.
γs(G)≤ α(G) + 1≤4α(G) / 3
γs is the fewest secure guards. α is the largest group of mutually nonadjacent vertices. The statement assumes α ≥ 3.
First, the game
A secure guard has to move—and leave no hole behind.
Answer
When an unguarded vertex is attacked, one adjacent guard swaps into it.
Stay safe
After that swap, every vertex must still be covered. The smallest team that always can do this is γs.
What does P₅-free mean? The network contains no five-vertex route whose only links are the four consecutive ones. That missing pattern forces surprisingly strong global structure.
Interactive proof map
Every possible graph walks through one of these doors.
- Connected P₅-free graph
- Dominating P₃ or dominating clique
- Path, clique 1–2, and triangle branches close
- Large clique: no cross-edge closes directly
- Cross-edge forces a dominating P₃
- Every branch reaches γs ≤ α + 1
current stepclosed branchnot opened yet
Logical dependencyThe all-orders proof does not depend on bounded SAT searches. Computation checks examples and local lemmas only.
Why 4/3 is exact
A ceiling is only sharp when something touches it.
4 ÷ 3
The icosahedral complement needs four guards although α = 3.
An exhaustive verifier checks all 220 triples and finds no secure one; 435 four-sets are secure.
Explore the 12-vertex graph ↗α + 1
No graph in the class can require more than one guard beyond α.
For α ≥ 3, α + 1 ≤ 4α/3. So every graph stays at or below the witness ratio.
Read the formal assembly ↗How the proof was found
The wrong turns left useful landmarks.
- 01
The stronger guess failed
The 12-vertex witness disproved γs ≤ α, but exposed the sharp lower ratio 4/3.
- 02
Easy graph structures fell away
Cut vertices, dominating pairs, and dominating three-vertex paths were proved to satisfy γs ≤ α + 1.
- 03
Cliques became the whole battlefield
Triangles were closed first. Larger minimal dominating cliques split into private regions and multi-hub neighbours.
- 04
A tempting edge lemma broke
A 12-vertex SAT witness killed the claim that every dominating edge extends directly to a secure triple. The proof target was changed instead of forced.
- 05
The last cross edge became a path
A private-region edge forces one hub plus its two endpoints to dominate the graph. That drops the final case back into the solved path branch.
Evidence boundary
A proof, corroboration, and one honest gate.
The theorem is an all-orders mathematical argument. Three independent proof reviews reconstructed its crucial cross-edge case. Finite computation is supporting evidence, not the logical foundation.
3independent proof reviewsall passed after precision fixes
11,264exact local modelsstructural checker, zero failures
648cross-edge checkseach produced the dominating P₃
Pendingconventional peer reviewthe repository is the auditable preprint package
Solved—and not claimed beyond scope
The coefficient question is closed for the published connected α ≥ 3 class.
- Solved: the best universal coefficient is 4/3.
- Still open here: a clean classification of every equality graph.
- Finite evidence only: whether the 12-vertex witness is minimum order.
- Outside the theorem: α = 2, disconnected graphs, or graphs containing an induced P₅.