We prove Graffiti 290: for every connected simple graph \(G\) of order \(n\) and girth at least five, \[ -\lambda_{n-1}(A)\;\le\;\frac{m}{\overline{\operatorname{Gr}}}, \] where \(\lambda_{n-1}\) is the second-smallest adjacency eigenvalue, \(m\) is the number of edges, and \(\overline{\operatorname{Gr}}\) is the mean of the gravity matrix over all \(n^2\) entries. The proof actually gives the stronger statement \(\max_i |\lambda_i(A)| \le m/\overline{\operatorname{Gr}}\). The chain is the same three lemmas used for Graffiti 292 — a degree-sum bound on mean gravity, the trace identity \(\operatorname{tr}(A^2)=2m\), and Reiman's \(C_4\)-free edge bound — closed by a quartic \(Q(t)\) whose shift \(Q(u+5)\) has exclusively positive coefficients. Orders \(n\le 7\) are dispatched by exact rational arithmetic. Verification uses four independent batteries — symbolic reduction, exact exhaustive small cases (34 girth-\(\ge 5\) graphs), a named-graph battery including Hoffman–Singleton, and a from-scratch independent reimplementation using LCF-constructed cages, random trees, and random girth-pruned graphs. Novelty is stated provisionally.
Let \(G\) be a connected simple graph on \(n\) vertices with adjacency matrix \(A\) and edge set of cardinality \(m\). Its gravity matrix (Brewster–Dinneen–Faber convention, reproduced by Roucairol–Cazenave and used verbatim in our companion Graffiti 292 proof) is
and \(\overline{\operatorname{Gr}}\) is the mean of all \(n^2\) entries. Order the adjacency eigenvalues \(\lambda_1 \ge \lambda_2 \ge \cdots \ge \lambda_n\); the second-smallest is \(\lambda_{n-1}\). Graffiti 290 (page 79 of Fajtlowicz's Written on the Wall, statement verified by direct transcription of the scan) asserts:
As of September 2024 the conjecture was listed open in Roucairol–Cazenave's Table 1 after search algorithms (NMCS, LNMCS, NRPA, UCT, GBFS, BEAM, GRAVE, RAVE) failed to refute it. The paper's erratum notes that the Aouchiche–Hansen gravity convention would make 290 trivially refutable; the Written on the Wall definition (used here) blocks all such counterexamples.
Proof. Since \(d(u,v)\ge 1\) for \(u \ne v\), \[ \overline{\operatorname{Gr}} =\frac{1}{n^2(n-1)}\sum_{u\ne v}\frac{d(u)d(v)}{d(u,v)} \le\frac{1}{n^2(n-1)}\Bigl(\sum_v d(v)\Bigr)^{\!2} = \frac{4m^2}{n^2(n-1)}, \] and division by \(m\) followed by reciprocation gives the claim. ∎
Proof. \(\sum_i \lambda_i^2 = \operatorname{tr}(A^2) = 2m\). ∎
Proof. By Lemma 2 it suffices to prove \(\sqrt{2m}\le m/\overline{\operatorname{Gr}}\); by Lemma 1 it suffices that \(\sqrt{2m}\le n^2(n-1)/(4m)\), i.e. \(n^4(n-1)^2\ge 32 m^3\). The right side is monotone in \(m\), so by Lemma 3 it suffices that \(n^4(n-1)^2 \ge 32 B(n)^3\), which simplifies to \[ 2n(n-1)^2 \ge \bigl(1+\sqrt{4n-3}\bigr)^3.\tag{1} \] Substituting \(t=\sqrt{4n-3}\), \(n=(t^2+3)/4\) and clearing 32 gives \[ 32\bigl(2n(n-1)^2-(1+t)^3\bigr) = (t+1)^2\,Q(t),\qquad Q(t)=t^4-2t^3+4t^2-38t-29. \] Writing \(t=u+5\) yields \[ Q(u+5) = u^4 + 18u^3 + 124u^2 + 352u + 256, \] whose coefficients are all strictly positive, so \(Q(t)>0\) for every \(t\ge 5\), i.e. every \(n\ge 7\). The endpoints \(n=5\) (value \(108-20\sqrt{17}\approx 25.54\)) and \(n=6\) (value \(236-24\sqrt{21}\approx 126.02\)) are strictly positive by exact arithmetic. For \(n\le 7\), all 34 connected girth-\(\ge 5\) graphs are verified exactly (Sturm counts of the adjacency characteristic polynomial roots below the rational bound \(-m/\overline{\operatorname{Gr}}\)). ∎
The terminal quartic is the entire analytic content of the argument:
Q(t) = t^4 - 2 t^3 + 4 t^2 - 38 t - 29 Q(u+5) = u^4 + 18 u^3 + 124 u^2 + 352 u + 256 — all coefficients strictly positive 32(2n(n-1)^2 - (1+t)^3) = (t+1)^2 Q(t) n=5 endpoint: 108 - 20 sqrt(17) ≈ 25.5379 > 0 n=6 endpoint: 236 - 24 sqrt(21) ≈ 126.0182 > 0
Four independent batteries, no shared code between the primary certifiers and the independent reimplementation. A failure at any battery would block publication.
| Battery | Method | Coverage | Status |
|---|---|---|---|
| 1. Named-graph battery | exact gravity means (rational) + numeric spectra | C₅, C₆, C₇, Petersen, Heawood, Pappus, Desargues, Möbius–Kantor, dodecahedron, Hoffman–Singleton, path P₁₀, star K₁,₉, spider (3,3,3), McGee 7-cage, Tutte–Coxeter 8-cage | PASS |
| 2. Symbolic reduction | SymPy exact factorization | factorization \((t+1)^2 Q(t)\), shifted coefficients [1, 18, 124, 352, 256], exact endpoints n=5, 6 | PASS |
| 3. Exhaustive exact small cases | exact rational gravity + Sturm root counts of adjacency characteristic polynomial | all 34 connected girth ≥ 5 graphs with 2 ≤ n ≤ 7 from the graph atlas | PASS |
| 4. Independent reimplementation | from-scratch: LCF cages, hand-rolled Hoffman–Singleton (pentagon/pentagram), separate gravity accumulator | HS, Petersen, Heawood, C₅, K₂, K₁,₂₀, McGee, Tutte–Coxeter, 60 random trees (2 ≤ n ≤ 60), 40 random girth-pruned graphs | PASS |
Every entry is derived from an exact rational gravity mean; the last column reports the certified inequality margin \(m/\overline{\operatorname{Gr}} - (-\lambda_{n-1})\). Positive means the bound holds; the strong pattern is that the margin grows quickly with \(n\).
| Graph | n | m | −λₙ₋₁ | m / Gr | margin |
|---|---|---|---|---|---|
| C₅ | 5 | 5 | 1.6180 | 8.333 | +6.715 |
| C₆ | 6 | 6 | 1.0000 | 13.500 | +12.500 |
| C₇ | 7 | 7 | 1.8019 | 20.045 | +18.244 |
| Petersen | 10 | 15 | 2.0000 | 25.000 | +23.000 |
| Heawood (6-cage) | 14 | 21 | 1.4142 | 57.909 | +56.495 |
| Möbius–Kantor | 16 | 24 | 1.7321 | 80.842 | +79.110 |
| Pappus | 18 | 27 | 1.7321 | 108.000 | +106.268 |
| Desargues | 20 | 30 | 2.0000 | 141.527 | +139.527 |
| McGee (7-cage) | 24 | 36 | 2.3429 | 210.286 | +207.943 |
| Tutte–Coxeter (8-cage) | 30 | 45 | 2.0000 | 362.500 | +360.500 |
| Hoffman–Singleton | 50 | 175 | 3.0000 | 312.500 | +309.500 |
All 34 connected simple graphs of order \(2\le n\le 7\) with girth at least five (path graphs, trees of every shape, C₅, C₆, C₇, and the small trees on 7 vertices) are enumerated from NetworkX's graph atlas. For each graph, the gravity mean is computed as an exact rational number \(m/\overline{\operatorname{Gr}}\in\mathbb{Q}\), and the adjacency characteristic polynomial is passed to SymPy's Sturm-based root counter to count roots strictly below \(-m/\overline{\operatorname{Gr}}\). At most one such root is permitted; if there is none, only the smallest root can fall below, which means \(-\lambda_{n-1}\le m/\overline{\operatorname{Gr}}\). Every one of the 34 graphs satisfies this. No graph produced a root at all in the offending region.
The Battery 4 script constructs the Hoffman–Singleton graph by the classical pentagon/pentagram recipe — five pentagons \(P_h\), five pentagrams \(Q_h\), with joins \(P_{h,i} \sim Q_{k,\,hk+i\bmod 5}\) — and separately verifies via A² and A³ that the graph is 7-regular, triangle-free, C₄-free, and contains a 5-cycle (hence girth 5). It uses its own gravity accumulator (no reuse of Battery 1's code) and its own path/cage constructions via LCF notation. Every check for 290 passes, including on 60 random trees generated by \texttt{networkx.random\_labeled\_tree} and 40 random girth-pruned graphs.
Graffiti 290 falls out of the exact chain that settles Graffiti 292 (companion whitepaper, a-proof-of-graffiti-292.html). Because the 292 terminal already proves \(n/\overline{\operatorname{Gr}} \ge \sqrt{2m}\) for \(n\ge 7\), whenever \(m \ge n\) the 290 target \(m/\overline{\operatorname{Gr}}\) exceeds \(n/\overline{\operatorname{Gr}}\ge\sqrt{2m}\ge |\lambda|\) automatically. The quartic \(Q(t)\) above absorbs the remaining sparse cases (trees, forests, unicyclic girth-\(\ge 5\) graphs where \(m Dependencies: Python 3.13, SymPy 1.14, NetworkX 3.5, NumPy 2.3. Exact arithmetic on the decisive rung; floating point is only used for numeric spectra in the named-graph table.6. Novelty status — stated provisionally
7. Reproduction protocol
python -m pip install sympy networkx numpy
python verify_290_symbolic.py # factorization, shift positivity, endpoints
python verify_290_small_cases.py # exhaustive n≤7, exact rational gravity, Sturm counts
python independent_check_284_290.py # independent reimplementation, 60 trees + 40 pruned
8. Artifact ledger
Artifact Purpose manuscript-graffiti-290.md Markdown proof with full derivations verify_290_symbolic.py · output Symbolic reduction: (t+1)²Q(t), shift positivity, endpoints verify_290_small_cases.py · output Exhaustive small-case + named-graph batteries (exact rational gravity, Sturm root count) independent_check_284_290.py · output Independent reimplementation (shared with the 284 refutation package) claim-ledger.json Claim-by-claim evidence map (covers 290 proof + 284 refutation verification + 295 attack state) wow-p79-bot.png Primary source scan of the page-79 conjecture statement SHA256SUMS.txt Integrity ledger References
