Graffiti 284 asserts that for every graph of girth at least five, the minimum dual degree is at most the negative of the smallest distance-matrix eigenvalue. The Hoffman–Singleton graph is 7-regular of girth 5 and its distance matrix has smallest eigenvalue \(-4\); the conjecture would require \(7\le 4\), which is false. This note records an independent, fully exact integer-only verification of the refutation. The strongly-regular identity \(A^2+A-6I=J\) and the diameter-2 relation \(D=2(J-I)-A\) are proved by integer matrix arithmetic, forcing the distance spectrum to be \(\{91,\,1^{21},\,(-4)^{28}\}\) with no numeric approximation. A second construction from the pentagon/pentagram recipe reproduces the check. Priority for the counterexample is credited to the Capy Build agent run of 22 July 2026; our contribution is the exact verification chain and the equality-case context.
From page 79 of Fajtlowicz's Written on the Wall, verbatim (statement fidelity re-established by direct vision transcription of the scanned page; local artifact wow-p79-bot.png):
The dual degree of a vertex \(v\) is \(d^*(v)=\frac{1}{d(v)}\sum_{u\sim v} d(u)\), the mean degree of its neighbors. Aouchiche & Hansen (2014, LAA 458) list this conjecture in their distance-spectra survey, state that "as far as we know, the above conjecture remains open", and observe that the Petersen graph attains equality, \(\delta^* = -\partial_n = 3\). Roucairol & Cazenave (2024) also list 284 open; their edge-flip searches to \(n=50\) found nothing — unsurprisingly, since the only counterexample in that range appears to be a single strongly regular graph their heuristics would essentially never hit.
Let \(G\) be the Hoffman–Singleton graph: 50 vertices, 175 edges, 7-regular, girth 5, diameter 2 — the third Moore graph of girth 5, after \(C_5\) and Petersen. Every step below is integer arithmetic; scripts are in verify_284_hoffman_singleton_exact.py with independent second construction in independent_check_284_290.py.
The integer matrix equation is verified entry-by-entry: this is the standard SRG(50, 7, 0, 1) identity. Consequences: on the all-ones vector, \(A\mathbf 1 = 7\mathbf 1\) (regularity); on \(\mathbf 1^\perp\), every adjacency eigenvalue \(\mu\) satisfies \(\mu^2 + \mu - 6 = 0\), so \(\mu \in \{2,-3\}\). Trace conditions \(7 + 2a - 3b = 0\), \(a + b = 49\), \(49 + 4a + 9b = 350\) force multiplicities \(a = 28\), \(b = 21\).
Exact BFS certifies every off-diagonal distance is 1 (on edges) or 2 (on non-edges), so \(D_{uv} = 1\cdot[u\sim v] + 2\cdot[u\not\sim v, u\ne v]\), which matches \(2(J-I)-A\) entry-by-entry.
By Lemma 2, \(D = 2(J-I) - A\). On the all-ones vector \(D\mathbf 1 = (2(n-1) - 7)\mathbf 1 = 91\mathbf 1\). On \(\mathbf 1^\perp\), \(J\) acts as \(0\), so \(D\) acts as \(-2I - A\), giving eigenvalues \(-2-\mu\): namely \(-2-2 = -4\) (with multiplicity 28) and \(-2-(-3) = 1\) (with multiplicity 21).
Since the graph is 7-regular, every vertex has dual degree \(7\). The conjecture requires \(7 \le -\partial_n = 4\), which is false. The excess of the true left side over the claimed right side is exactly \(7-4=3\). ∎
Aouchiche & Hansen record that the Petersen graph attains equality in 284: dual degree \(3\), \(-\partial_n = 3\). By the same \(D = 2(J-I) - A\) identity, on the (hypothetical) 57-regular Moore graph of order \(3250\) — the only remaining candidate for a degree-57 girth-5 diameter-2 SRG — the eigenvalue \(\mu = -8\) of \(A\) would give \(\partial_n = -6\), and dual degree \(= 57\) yields a would-be violation of margin \(51\). The pattern on the four candidates is:
| Graph | n | k | \(-\partial_n\) | dual deg. | status |
|---|---|---|---|---|---|
| \(C_5\) | 5 | 2 | 3+ | 2 | holds |
| Petersen | 10 | 3 | 3 | 3 | equality |
| Hoffman–Singleton | 50 | 7 | 4 | 7 | FAILS (margin 3) |
| hypothetical 57-Moore | 3250 | 57 | 6 | 57 | FAILS (margin 51 if it exists) |
Because girth-5 diameter-2 graphs are exactly the Moore graphs (degree–diameter), the counterexample family among diameter-2 girth-5 graphs is as small as it could be. All other girth-5 graphs have diameter at least 3, where distances spread and both sides of the conjecture increase — consistent with the Roucairol–Cazenave searches finding no other violation.
The verification is repeated in independent_check_284_290.py using a from-scratch construction of Hoffman–Singleton — pentagons \(P_h\) (5-cycles on vertices \((p,h,i)\) for \(i \in \mathbb Z_5\)), pentagrams \(Q_h\) (edges \((q,h,i)\sim(q,h,i+2)\)), and joins \((p,h,i)\sim(q,k,\,hk+i \bmod 5)\). Triangle- and \(C_4\)-freeness are verified by \(\operatorname{tr}(A^3)=0\) and the codegree condition on \(A^2\); the 5-cycle exists explicitly. This construction shares no code with the primary verifier and produces the same distance spectrum with \(\partial_n = -4\).
python -m pip install networkx numpy sympy python verify_284_hoffman_singleton_exact.py # integer-only chain: SRG identity, D formula, spectrum, margin python independent_check_284_290.py # from-scratch pentagon/pentagram construction, cross-check
| Artifact | Purpose |
|---|---|
| note-graffiti-284-refutation.md | Markdown source of this note |
| verify_284_hoffman_singleton_exact.py · output | Integer-only exact verification chain |
| independent_check_284_290.py · output | Independent second construction and cross-check |
| claim-ledger.json | Claim-by-claim evidence map |
| wow-p79-bot.png | Primary source scan of the conjecture |
| SHA256SUMS.txt | Integrity ledger |
