# A proof of Graffiti 290

**Status:** candidate proof package, independently reproducible from the accompanying scripts.
**Date:** 23 July 2026.
**Companion result:** proved by the same lemma chain as Graffiti 292 (AGNT Labs, 23 July 2026).

## Abstract

Let \(G\) be a connected simple graph of order \(n\), size \(m\), and girth at least five (acyclic graphs count as infinite girth). Graffiti conjecture 290 (*Written on the Wall*, page 79) states that the negative of the second smallest adjacency eigenvalue is at most \(m/\overline{\mathrm{Gr}}\), where \(\overline{\mathrm{Gr}}\) is the mean of all \(n^2\) entries of the gravity matrix. We prove the conjecture — in the stronger form that **every** adjacency eigenvalue has absolute value at most \(m/\overline{\mathrm{Gr}}\) — by the same three-lemma chain that settles Graffiti 292: a degree-sum bound for mean gravity, the trace bound \(\lambda^2 \le 2m\), and Reiman's edge bound for \(C_4\)-free graphs. The terminal inequality reduces to a quartic with positive shifted coefficients. Orders \(n \le 7\) are dispatched by exact exhaustive enumeration.

## The statement

Verbatim from *Written on the Wall*, page 79 (statement fidelity confirmed by direct vision transcription of the scan; local artifact `wow-p79-bot.png`):

> **290.** If girth is ≥ 5 then the − 2nd smallest eigenvalue ≤ size/meangravity.

Conventions (Brewster–Dinneen–Faber / Roucairol–Cazenave, identical to the 292 package):

- "size" is the number of edges \(m\); unqualified "eigenvalue" is an adjacency eigenvalue (the Wall says "of Laplacian" when it means the Laplacian, cf. items 286, 287, 297).
- Gravity matrix: \(\operatorname{Gr}_{uv} = 0\) if \(u = v\), else \(d(u)d(v)/\bigl((n-1)\,d(u,v)\bigr)\); \(\overline{\operatorname{Gr}}\) is the mean over all \(n^2\) entries.
- Eigenvalues ordered \(\lambda_1 \ge \dots \ge \lambda_n\); the second smallest is \(\lambda_{n-1}\). The conjecture asserts \(-\lambda_{n-1} \le m/\overline{\operatorname{Gr}}\).
- Definition risk note: Roucairol–Cazenave (arXiv:2409.18626, erratum §5.2) report that 290 is trivially falsifiable under Aouchiche–Hansen's variant gravity definition but "seemingly impossible" under the Brewster et al. definition — which is the Wall's own definition (page 52) and the one used here.

## Lemma 1 (gravity bound)

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)},
\qquad\text{hence}\qquad
\frac{m}{\overline{\operatorname{Gr}}} \ge \frac{n^2(n-1)}{4m}.
\]

## Lemma 2 (trace bound)

\(\sum_i \lambda_i^2 = \operatorname{tr}(A^2) = 2m\), so \(|\lambda_i| \le \sqrt{2m}\) for every \(i\); in particular \(-\lambda_{n-1} \le \sqrt{2m}\). (If \(\lambda_{n-1} \ge 0\) the conjecture is trivial since the right side is positive.)

## Lemma 3 (Reiman)

A \(C_4\)-free graph — in particular any graph of girth \(\ge 5\) — satisfies \(m \le B(n) = \tfrac{n}{4}\bigl(1 + \sqrt{4n-3}\bigr)\).

## Terminal inequality

It suffices to prove \(\dfrac{n^2(n-1)}{4m} \ge \sqrt{2m}\), i.e. \(n^4(n-1)^2 \ge 32 m^3\). 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 .
\]
Substituting \(t = \sqrt{4n-3}\), \(n = (t^2+3)/4\) and clearing denominators:
\[
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 .
\]
The shift \(t = u + 5\) gives
\[
Q(u+5) = u^4 + 18u^3 + 124u^2 + 352u + 256,
\]
with all coefficients positive, so \(Q(t) > 0\) for every \(t \ge 5\), i.e. every \(n \ge 7\). The endpoints \(n = 5\) \(\bigl(108 - 20\sqrt{17} > 0\bigr)\) and \(n = 6\) \(\bigl(236 - 24\sqrt{21} > 0\bigr)\) are checked exactly. Orders \(2 \le n \le 7\) (34 connected girth-\(\ge 5\) graphs, trees included) are verified by exact rational arithmetic: Sturm root counts of the characteristic polynomial against the rational bound \(m/\overline{\operatorname{Gr}}\).

Combining: for every connected girth-\(\ge 5\) graph,
\[
-\lambda_{n-1} \;\le\; \sqrt{2m} \;\le\; \frac{n^2(n-1)}{4m} \;\le\; \frac{m}{\overline{\operatorname{Gr}}} . \qquad\blacksquare
\]

## Remarks

1. The proof gives the stronger statement \(\max_i |\lambda_i| \le m/\overline{\operatorname{Gr}}\): conjecture 290 asks only for \(-\lambda_{n-1}\).
2. The chain is exactly the Graffiti 292 chain with the right-hand side scaled by \(m/n\); since the 292 terminal already gives \(n/\overline{\operatorname{Gr}} \ge \sqrt{2m}\) for \(n \ge 7\), any \(m \ge n\) case of 290 follows from 292 directly. The quartic above absorbs the sparse cases \(m < n\) as well, so no case split is needed.
3. Equality analysis: the chain is loose (Lemma 1 collapses all distances to 1), so no girth-\(\ge 5\) graph attains equality; the numerically smallest observed margin is C5 (\(-\lambda_{n-1} \approx 1.618\) vs \(8.333\)).

## Verification batteries (all PASS)

1. **Symbolic** (`verify_290_symbolic.py`): factorization \((t+1)^2 Q(t)\), shifted-coefficient positivity, exact endpoints \(n = 5, 6\).
2. **Exhaustive exact small cases** (`verify_290_small_cases.py`): all 34 connected girth-\(\ge 5\) graphs with \(2 \le n \le 7\) from the graph atlas; rational mean gravity; Sturm counts of adjacency characteristic polynomial roots below \(-m/\overline{\operatorname{Gr}}\) (at most one permitted).
3. **Named-graph battery** (same script): C5–C7, Petersen, Heawood, Pappus, Desargues, Möbius–Kantor, dodecahedron, Hoffman–Singleton, paths, stars, spiders — all satisfied with margin \(\ge 6.7\).
4. **Independent reimplementation** (`independent_check_284_290.py`): written from the frozen statement, different HS construction (pentagon/pentagram), different gravity accumulation, LCF-constructed McGee and Tutte–Coxeter cages, 60 random trees, 40 random girth-pruned graphs — all pass.

## Priority and scope

The proof appears to be the first publicly documented one we could find: Roucairol–Cazenave (September 2024) list 290 as open; the Aouchiche–Hansen distance-spectra survey does not treat it (adjacency-side statement); searches for the statement and technique (excluding our own indexed artifacts) return nothing. Priority is claimed only as "first publicly documented instance found in our bounded search," not as historically adjudicated. Produced with AI assistance (AGNT orchestrator); all decisive steps are machine-verified exact computations reproducible from the scripts in this directory.