Counterexamples, Spectral Obstructions, and Deletion Stability for WOW-284

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.SP — Spectral Theory

Contributed by Samuil Petkov ↗

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 −λmin⁡(D)-\lambda_{\min}(D), where DD 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 3838, 3939, 4040, 4242 and 5050 vertices and study the structure of regular counterexamples. For a connected kk-regular graph GG of girth at least five and diameter three, we prove that δ∗(G)+λmin⁡(D)=2k−2−max⁡θ(θ+1)2\delta^*(G)+\lambda_{\min}(D)=2k-2-\max_\theta(\theta+1)^2, the maximum being over the nonprincipal adjacency eigenvalues, so strict failure is a spectral window condition. The closed window ∣θ+1∣≤2k−2|\theta+1|\le\sqrt{2k-2} alone, without any diameter assumption, forces ∣V(G)∣<(k+2)(k2+3)/6|V(G)|<(k+2)(k^2+3)/6 when k≥4k\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 5050 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-5757 Moore graph, if one exists, remains a connected strict counterexample after the removal of any 5656 vertices. Every strict counterexample has at least 1515 vertices, and an exhaustive search excludes orders up to 1919. The strict induced subgraphs of the Hoffman-Singleton graph of orders 3636 to 5050 are classified up to automorphism; among them are three further irregular counterexamples of order 4040.

Author comments: This 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/.

Provenance statement

OpenAI ChatGPT-5.6 Sol Pro assisted with adversarial proof checking, proof exploration, and Lean formalization. Codex also assisted with supplementary proof arguments. Anthropic Claude (Claude Code) was used only to prepare this Hexagon deposit. The author assumes full responsibility for the mathematics, attribution, and conclusions.

Tools used

OpenAI
ChatGPTVersion GPT-5.6 Sol Pro
OpenAI
Codex

References

  1. 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
  2. Siemion Fajtlowicz. Written on the wall: Conjectures derived on the basis of the program Galatea Gabriella Graffiti . Technical report, University of Houston, 1998.
  3. 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
  4. 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
  5. 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
  6. 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
  7. Miquel À ngel Fiol. Quotient-polynomial graphs. Linear Algebra and its Applications , 488: 0 363--376, 2016. 10.1016/j.laa.2015.09.053.DOI
  8. 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
  9. 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
  10. 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
  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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
  8. 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
  9. 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
  10. 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
  11. Brendan D. McKay and Adolfo Piperno. Practical graph isomorphism, II . Journal of Symbolic Computation , 60: 0 94--112, 2014. arXiv:1301.1493.arXiv
  12. 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
  13. 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
  14. 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
  15. 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
  16. Aaron Meurer et al. SymPy : Symbolic computing in Python . PeerJ Computer Science , 3: 0 e103, 2017. 10.7717/peerj-cs.103.DOI
  17. 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
  18. 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
  19. 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

  1. 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