no. 16 · Tuesday 17 November 2026
Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284
Abstract
WOW-284 is a Graffiti conjecture asserting that every connected graph of order at least three and girth at least five has minimum dual degree at most $-λ_{\min}(D)$, where $D$ is the distance matrix and the dual degree of a vertex is the average degree of its neighbors. We refute it with exact counterexamples on $38$, $39$, $40$, $42$ and $50$ vertices and study the structure of regular counterexamples. For a connected $k$-regular graph $G$ of girth at least five and diameter three, we prove that $δ^*(G)+λ_{\min}(D)=2k-2-\max_θ(θ+1)^2$, the maximum being over the nonprincipal adjacency eigenvalues, so strict failure is a spectral window condition. The closed window $|θ+1|\le\sqrt{2k-2}$ alone, without any diameter assumption, forces $|V(G)|<(k+2)(k^2+3)/6$ when $k\ge4$, and an integral excess matrix derived from the optimal polynomial sharpens this bound for diameter-three counterexamples. Every regular strict counterexample has degree at least six and diameter at most four, and in degree six it has at most $50$ vertices. Under vertex deletion, the Hoffman-Singleton graph remains a strict counterexample after the removal of any five vertices, while an explicit six-vertex deletion destroys strictness. A degree-$57$ Moore graph, if one exists, remains a connected strict counterexample after the removal of any $56$ vertices. Every strict counterexample has at least $15$ vertices, and an exhaustive search excludes orders up to $19$. The strict induced subgraphs of the Hoffman-Singleton graph of orders $36$ to $50$ are classified up to automorphism; among them are three further irregular counterexamples of order $40$.
- comments
- 44 pages. Exact computations and Lean 4.31 certificates
- fields
- Combinatorics, Spectral Theory