Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284
Version 1 / Nov 18, 2026/ arXiv: 2607.27452 / CC BY 4.0
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 , where 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 , , , and vertices and study the structure of regular counterexamples. For a connected -regular graph of girth at least five and diameter three, we prove that , the maximum being over the nonprincipal adjacency eigenvalues, so strict failure is a spectral window condition. The closed window alone, without any diameter assumption, forces when , 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 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- Moore graph, if one exists, remains a connected strict counterexample after the removal of any vertices. Every strict counterexample has at least vertices, and an exhaustive search excludes orders up to . The strict induced subgraphs of the Hoffman-Singleton graph of orders to are classified up to automorphism; among them are three further irregular counterexamples of order .
Provenance statement
Tools used
- OpenAI
- ChatGPTVersion GPT-5.6 Sol Pro
- OpenAI
- Codex
References
- Mustapha Aouchiche and Pierre Hansen. Distance spectra of graphs: A survey. Linear Algebra and its Applications , 458: 0 301--386, 2014. 10.1016/j.laa.2014.06.010.DOI
- Siemion Fajtlowicz. Written on the wall: Conjectures derived on the basis of the program Galatea Gabriella Graffiti . Technical report, University of Houston, 1998.
- Alan J. Hoffman and Robert R. Singleton. On Moore graphs with diameters 2 and 3. IBM Journal of Research and Development , 4 0 (5): 0 497--504, 1960. 10.1147/rd.45.0497.DOI
- Capy Build . CE10 : Refuting Graffiti 284. Public agent transcript, 2026. URL https://tokiwa.space/f/more-front-minute.pdf. Agent run dated 22 July 2026, 18:14--18:22 UTC.link
- Nathan Wilbanks and Annie . Graffiti 284 refuted by Hoffman--Singleton : An independent exact verification. AGNT Labs verification note, 2026. URL https://agnt.gg/whitepapers/graffiti-284-refutation. Dated 23 July 2026.link
- Aditi Howlader and Pratima Panigrahi. On the distance spectrum of minimal cages and associated distance biregular graphs. Linear Algebra and its Applications , 636: 0 115--133, 2022. 10.1016/j.laa.2021.11.014.DOI
- Miquel À ngel Fiol. Quotient-polynomial graphs. Linear Algebra and its Applications , 488: 0 363--376, 2016. 10.1016/j.laa.2015.09.053.DOI
- Hiroshi Nozaki. Linear programming bounds for regular graphs. Graphs and Combinatorics , 31 0 (6): 0 1973--1984, 2015. 10.1007/s00373-015-1613-7.DOI
- Sebastian M. Cioab ă , Jack H. Koolen, Hiroshi Nozaki, and Jason R. Vermette. Maximizing the order of a regular graph of given valency and second eigenvalue. SIAM Journal on Discrete Mathematics , 30 0 (3): 0 1509--1525, 2016. 10.1137/15M1030935.DOI
- J ö rgen Backelin. Sizes of the extremal girth 5 graphs of orders from 40 to 49, 2015. arXiv:1511.08128.arXiv
Show all 29 referencesShow fewer references
- Paul R. Hafner. The Hoffman--Singleton graph and its automorphisms. Journal of Algebraic Combinatorics , 18 0 (1): 0 7--12, 2003. 10.1023/A:1025136524481.DOI
- Leif K. Jørgensen. Girth 5 graphs from relative difference sets. Discrete Mathematics , 293 0 (1--3): 0 177--184, 2005. 10.1016/j.disc.2004.08.029.DOI
- M. O'Keefe and Pak-Ken Wong. A smallest graph of girth 5 and valency 6. Journal of Combinatorial Theory, Series B , 26 0 (2): 0 145--149, 1979. 10.1016/0095-8956(79)90052-2.DOI
- Pak-Ken Wong. On the uniqueness of the smallest graph of girth 5 and valency 6. Journal of Graph Theory , 3 0 (4): 0 407--409, 1979. 10.1002/jgt.3190030413.DOI
- Mikhail Klin, Mikhail Muzychuk, and Matan Ziv-Av. Higmanian rank-5 association schemes on 40 points. Michigan Mathematical Journal , 58 0 (1): 0 255--284, 2009. 10.1307/mmj/1242071692.DOI
- Edwin R. van Dam and Willem H. Haemers. Which graphs are determined by their spectrum? Linear Algebra and its Applications , 373: 0 241--272, 2003. 10.1016/S0024-3795(03)00483-X.DOI
- Peter J. Cameron, Jean-Marie Goethals, Johan J. Seidel, and Ernest E. Shult. Line graphs, root systems, and elliptic geometry. Journal of Algebra , 43 0 (1): 0 305--327, 1976. 10.1016/0021-8693(76)90162-9.DOI
- Markus Meringer. Fast generation of regular graphs and construction of cages. Journal of Graph Theory , 30 0 (2): 0 137--146, 1999. 10.1002/(SICI)1097-0118(199902)30:2<137::AID-JGT7>3.0.CO;2-G.DOI
- Willem H. Haemers. Interlacing eigenvalues and graphs. Linear Algebra and its Applications , 226--228: 0 593--616, 1995. 10.1016/0024-3795(95)00199-2. URL https://doi.org/10.1016/0024-3795(95)00199-2.DOI
- Derek H. Smith and Roberto Montemanni. The Moore graph of diameter 2 and degree 57 via cyclic derangements. Axioms , 15 0 (5): 0 332, 2026. 10.3390/axioms15050332.DOI
- Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II . Journal of Symbolic Computation , 60: 0 94--112, 2014. arXiv:1301.1493.arXiv
- Drago š Cvetkovi ć , Peter Rowlinson, and Slobodan Simi ć . Spectral Generalizations of Line Graphs: On Graphs with Least Eigenvalue -2 . Cambridge University Press, 2004. 10.1017/CBO9780511751752.DOI
- Jack H. Koolen, Kefan Yu, Xiaoye Liang, Harrison Choi, and Greg Markowsky. Non-geometric distance-regular graphs of diameter at least 3 with smallest eigenvalue at least -3. European Journal of Combinatorics , 126: 0 104118, 2025. 10.1016/j.ejc.2024.104118.DOI
- Gary Greaves, Jack H. Koolen, Akihiro Munemasa, Yoshio Sano, and Tetsuji Taniguchi. Edge-signed graphs with smallest eigenvalue greater than -2. Journal of Combinatorial Theory, Series B , 110: 0 90--111, 2015. 10.1016/j.jctb.2014.07.006.DOI
- Mari é n Abreu, Martin Funk, Domenico Labbate, and Vito Napolitano. A family of regular graphs of girth 5. Discrete Mathematics , 308 0 (10): 0 1810--1815, 2008. 10.1016/j.disc.2007.04.031.DOI
- Aaron Meurer et al. SymPy : Symbolic computing in Python . PeerJ Computer Science , 3: 0 e103, 2017. 10.7717/peerj-cs.103.DOI
- Aric A. Hagberg, Daniel A. Schult, and Pieter J. Swart. Exploring network structure, dynamics, and function using NetworkX . In Proceedings of the 7th Python in Science Conference , pages 11--15, 2008. 10.25080/TCWV9851.DOI
- Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In Automated Deduction---CADE 28 , volume 12699 of Lecture Notes in Computer Science , pages 625--635. Springer, 2021. 10.1007/978-3-030-79876-5_37.DOI
- The mathlib Community . The Lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs , pages 367--381. Association for Computing Machinery, 2020. 10.1145/3372885.3373824.DOI
Version history
- v1 · 44 pagesSubmitted by Samuil PetkovThis is version 2 of arXiv:2607.27452 (https://arxiv.org/abs/2607.27452). The source code, exact certificates and build instructions are at https://github.com/SamPetkov/wow284 ; the verification scripts and data used in the paper are included in anc/.CurrentNov 17, 2026