A Proof of Graffiti 292:
The Least Positive Eigenvalue of Girth-Five Graphs

Nathan Wilbanks and Annie
AGNT Labs
Research Report · July 23, 2026 · revised July 24, 2026 (§2.5 addendum)
Artifacts & evidence set · SHA256SUMS · Proof PDF
Abstract

We prove Graffiti 292: for every connected simple graph \(G\) of order \(n\) and girth at least five, the least positive adjacency eigenvalue satisfies \[ \lambda_+(G)\;\le\;\frac{n}{\overline{\operatorname{Gr}}}, \] where the gravity matrix has off-diagonal entries \(d(u)d(v)/((n-1)\,d(u,v))\), zero diagonal, and mean taken over all \(n^2\) entries. The proof is a three-line argument. A degree-sum bound gives \(n/\overline{\operatorname{Gr}}\ge (n-1)n^3/(4m^2)\); the trace identity \(\operatorname{tr}(A^2)=2m\) gives \(\lambda_+\le\sqrt{2m}\); and Reiman's \(C_4\)-free edge bound \(m\le n(1+\sqrt{4n-3})/4\) closes the chain for every \(n\ge7\) via a polynomial whose shifted form has exclusively positive coefficients. Small orders are dispatched by exact exhaustive computation with rational root isolation. The package includes four independent verification batteries — exact gravity means on named cages, symbolic reduction, exact small-case enumeration, and a from-scratch independent reimplementation over 18,686 labeled graphs through order seven — plus full source scans, scripts, run logs, technical vector figures, and SHA-256 hashes. Novelty is stated provisionally: we found no prior resolution in the indexed literature, but priority is not claimed pending expert review.

Status. The proof and all executable checks pass. This is a complete candidate proof under the gravity normalization documented in the source corpus; it has not yet received external mathematical peer review. Historical priority is not claimed — see §6.

1. The conjecture

Let \(G\) be a connected simple graph on \(n\) vertices with adjacency matrix \(A\). Its gravity matrix is

$$\operatorname{Gr}_{uv}=\begin{cases}0,&u=v,\\[3pt]\dfrac{d(u)\,d(v)}{(n-1)\,d(u,v)},&u\ne v,\end{cases}$$

where \(d(u)\) is degree, \(d(u,v)\) is graph distance, and \(\overline{\operatorname{Gr}}\) is the mean of all \(n^2\) entries (diagonal zeros included). Graffiti 292 (page 80 of Fajtlowicz's Written on the Wall) asserts that if \(G\) has girth at least five, then the least positive adjacency eigenvalue obeys

$$\lambda_+(G)\;\le\;\frac{n}{\overline{\operatorname{Gr}}}.$$

As of the September 2024 Roucairol–Cazenave search survey, the conjecture was listed open after an exhaustive spectral search across cages, incidence graphs of projective planes, and random regular graphs of girth at least five.

2. The proof

1. Gravity Bound Gr ≤ 4m² / [n²(n−1)] ⇓ n / Gr ≥ (n−1)n³ / 4m² 2. Reiman C₄-Free Cap m ≤ B(n) = ¼ n (1 + √(4n−3)) ⇓ L(n) = (n−1)n³ / 4B(n)² 3. Polynomial Dominance L(n) ≥ √(2B(n)) for n ≥ 7 ⇓ [Trace: λ₊ ≤ √(2m)] n / Gr ≥ λ₊(G) Small Cases (n ≤ 6): Dispatched via exact rational root isolation over all 35 connected girth ≥ 5 graph-atlas isomorphism classes. General Cases (n ≥ 7): Analytical chain holds unconditionally via positive coefficient shift P(u+5) > 0.
Figure 1. Bounding chain structure for Graffiti 292. The problem splits into an algebraic lower bound \(L(n)\) derived from distance contraction and Reiman's edge cap, compared against the spectral trace upper bound \(R(n) = \sqrt{2B(n)}\).

2.1 A degree-sum lower bound for \(n/\overline{\operatorname{Gr}}\)

Lemma 1. If \(G\) has \(m\) edges, then
$$\frac{n}{\overline{\operatorname{Gr}}}\;\ge\;\frac{(n-1)\,n^3}{4m^2}.$$

Proof. Since \(d(u,v)\ge1\) 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)}\sum_{u\ne v}d(u)d(v) \le\frac{(2m)^2}{n^2(n-1)}=\frac{4m^2}{n^2(n-1)}. \] Taking reciprocals yields the claim. ∎

2.2 The trace bound

Lemma 2. Every adjacency eigenvalue \(\lambda\) satisfies \(|\lambda|\le\sqrt{2m}\).

Proof. If \(\lambda_1,\dots,\lambda_n\) are the adjacency eigenvalues, then \(\sum_i\lambda_i^2=\operatorname{tr}(A^2)=2m\). ∎

R = n / Gr λ₊(G) r = √(2m) Geometric Containment Mechanics 1. Inner Trace Hypersphere: tr(A²) = ∑ λᵢ² = 2m ⟹ ||λ||₂ = √(2m) Since λ₊ ≤ ||λ||₂, the positive eigenvalue is bounded above by the radius r = √(2m). 2. Outer Gravity Boundary: Distance d(u,v) ≥ 1 contracts mean gravity. Reiman cap m ≤ B(n) prevents radius expansion. Result: R > r for all n ≥ 7 unconditionally.
Figure 2. Geometric containment mechanism. The adjacency eigenvalue vector lies on the radius-\(r=\sqrt{2m}\) sphere in \(\mathbb{R}^n\) by the trace energy identity \(\operatorname{tr}(A^2) = 2m\). For \(n \ge 7\), Reiman's \(C_4\)-free edge bound prevents \(r\) from expanding fast enough to reach the outer gravity boundary \(R = n / \overline{\operatorname{Gr}}\), guaranteeing \(\lambda_+(G) \le R\).

2.3 Reiman's extremal edge bound

Lemma 3. If \(G\) contains no four-cycle, then
$$m\le B(n):=\frac{n}{4}\left(1+\sqrt{4n-3}\right).$$

A graph of girth at least five has no triangles or four-cycles, so the bound applies.

2.4 Closing the chain

Theorem. Graffiti 292 is true.

Proof. For \(n\ge7\), set \(t=\sqrt{4n-3}\), so \(n=(t^2+3)/4\) and \(t\ge5\). The left side of \[ \frac{(n-1)n^3}{4B(n)^2}\ge\sqrt{2B(n)}\tag{1} \] decreases with \(m\) while the right side increases, so Lemma 3 reduces the comparison to (1). Both sides are positive. Squaring (1), substituting \(n=(t^2+3)/4\), and clearing positive denominators reduces (1) to \(P(t)>0\), where \[ P(t)=2(t+1)^2\left(t^4-4t^3-2t^2-12t+1\right). \] Writing \(t=u+5\) gives, by direct expansion, \[ P(u+5)=2u^6+56u^5+632u^4+3600u^3+10400u^2+12480u+1152>0 \] for every \(u\ge0\). Hence, by Lemmas 1–3, \[ \frac{n}{\overline{\operatorname{Gr}}} \ge\frac{(n-1)n^3}{4m^2} \ge\sqrt{2m} \ge\lambda_+(G). \] For \(n\le6\), every connected simple graph of girth at least five is among the finite cases checked exactly below (the verifier covers all qualifying graphs through order seven). ∎

0 5 10 15 20 Bound Value 2 5 7 10 15 20 Graph Order (n) Crossover (n = 7) L(7) = 4.667 > R(7) = 4.583 L(n) = (n−1)n³ / 4B(n)² [~Θ(n)] R(n) = √(2B(n)) [~O(n^{0.75})] Gravity Lower Bound L(n) Eigenvalue Upper Cap R(n)
Figure 3. Analytical comparison of \(L(n)\) and \(R(n)\) for \(n \in [2, 20]\). For \(n \ge 7\), \(L(n) > R(n)\) strictly. As \(n \to \infty\), \(L(n)\) grows as \(\Theta(n)\) while \(R(n)\) grows as \(\Theta(n^{3/4})\), establishing asymptotic divergence.

The terminal polynomial is the final analytic step of the argument. Its factored and expanded forms, exact endpoint value, and shifted coefficient list are machine-verified:

cleared(t) = 2(t+1)^2 (t^4 - 4t^3 - 2t^2 - 12t + 1)
           = 2 t^6 - 4 t^5 - 18 t^4 - 40 t^3 - 50 t^2 - 20 t + 2
cleared(5) = 1152
cleared(t = u + 5) coefficients: [2, 56, 632, 3600, 10400, 12480, 1152]  — all strictly positive
Coefficient Profile of Shifted Polynomial P(u + 5) = ∑ cₖ uᵏ All coefficients cₖ > 0 ⟹ P(u+5) > 0 unconditionally for all u ≥ 0 (n ≥ 7) 2 u⁶ 56 u⁵ 632 u⁴ 3600 u³ 10400 u² 12480 u¹ 1152 u⁰ Logarithmic height scaling applied for visual clarity. Exact values indicated above each bar.
Figure 4. Coefficient spectrum of the shifted polynomial \(P(u+5) = 2u^6 + 56u^5 + 632u^4 + 3600u^3 + 10400u^2 + 12480u + 1152\). Because every coefficient \(c_k > 0\), \(P(u+5) > 0\) for every \(u \ge 0\); equivalently, the shifted polynomial has no nonnegative real root (Descartes' rule likewise gives no positive root).

2.5 A stronger, uniform bound (added in revision, July 24, 2026)

Theorem (uniform form). For every connected simple graph \(G\) of order \(n\ge2\) and girth at least five,
$$\lambda_+(G)\;\le\;n-1\;<\;n\;\le\;\frac{n}{\overline{\operatorname{Gr}}},$$

so Graffiti 292 holds with strict inequality, uniformly in \(n\) — with no edge-cap, no trace bound, no polynomial, and no finite case split.

Proof. A graph of girth at least five has no triangle and no four-cycle. Count the paths of length two ("cherries"): there are \(\sum_v\binom{d(v)}{2}\) of them. Triangle-freeness makes the two endpoints of each cherry non-adjacent; \(C_4\)-freeness means a non-adjacent pair has at most one common neighbour, so distinct cherries have distinct endpoint pairs. Hence cherries inject into non-edges: \[ \sum_v\binom{d(v)}{2}\;\le\;\binom{n}{2}-m. \] By Cauchy–Schwarz, \(\sum_v d(v)^2\ge(\sum_v d(v))^2/n=4m^2/n\), so \(\sum_v\binom{d(v)}{2}=\tfrac12\sum_v d(v)^2-m\ge \tfrac{2m^2}{n}-m\). Combining the two, \[ \frac{2m^2}{n}-m\;\le\;\frac{n(n-1)}{2}-m\qquad\Longrightarrow\qquad 4m^2\le n^2(n-1). \] Feeding this into Lemma 1 (unchanged), \[ \frac{n}{\overline{\operatorname{Gr}}}\;\ge\;\frac{(n-1)n^3}{4m^2}\;\ge\;\frac{(n-1)n^3}{n^2(n-1)}\;=\;n, \] that is \(\overline{\operatorname{Gr}}\le1\). Finally every adjacency eigenvalue obeys \(\lambda_+\le\rho(A)\le\Delta(G)\le n-1\). Chaining gives \(\lambda_+\le n-1

Attribution. This uniform argument was pointed out by Spanky McDoob (@59thProfile, private communication, July 2026). The counting inequality \(\sum_v\binom{d(v)}{2}\le\binom{n}{2}-m\) and its consequence \(4m^2\le n^2(n-1)\) are the classical Kővári–Sós–Turán / Reiman cherry-count; McDoob's contribution is the observation that this cruder bound composes with Lemma 1 to settle Graffiti 292 directly and in the strict form above, bypassing Reiman's sharp cap, the terminal polynomial, the \(n\ge7\) crossover, and the finite small-case check of §§2.3–4. The Reiman-based argument of §§2.1–2.4 is retained as an independent, sharper-constant companion and as the object of the machine-verification batteries. The uniform bound is verified exactly (symbolic reduction, exhaustive atlas \(n\le7\), and exact named cages) in verify_twopath_292.py.

3. Verification architecture

Four independent batteries, no shared code between the two reimplementations. A failure in any battery would block publication.

Table 1. Verification batteries and outcomes.
BatteryMethodCoverageStatus
1. Named-graph evaluatorexact gravity means + float spectrapaths, cycles, Petersen, Heawood, Pappus, Desargues, Möbius–Kantor, Hoffman–Singleton, random regular girth ≥ 5, graph atlas ≤ 7PASS
2. Symbolic reductionSymPy exact factorizationcleared polynomial, expansion, derivative, endpoint 1152, shifted coefficientsPASS
3. Exact small-case enumerationcharacteristic polynomials + rational root isolationall 35 connected girth ≥ 5 graphs through order 7PASS
4. Independent reimplementationfrom-scratch, no shared code: exact-integer inequality, hand-rolled graph engine, Fano-plane and Hoffman–Singleton constructionsanalytic bound at n = 7..199, 10³, 10⁴, 10⁵, 10⁶; exhaustive over all connected girth ≥ 5 graphs on n ≤ 6 (1,874 labeled) plus all n = 7 trees, cycles, and unicyclic graphs — 18,686 labeled graphs in total, dominated by the 16,807 labeled 7-vertex trees; the one bicyclic n = 7 class is covered by the atlas battery, and n = 7 is in any case covered by the analytic argument (t = 5); four named cagesPASS

4. Exact certificates

4.1 Named cages (exact gravity means, verified margins)

Table 2. Exact gravity means and verified inequality margins. The margin is \(\lambda_+ - n/\overline{\operatorname{Gr}}\); strict negativity is required for the bound to hold with room.
Graphnmgirth\(\lambda_+\)\(n/\overline{\operatorname{Gr}}\)margin
\(C_5\)5550.6180348.333333−7.715299
Petersen101551.00000016.666667−15.666667
Heawood142161.41421438.606061−37.191847
Hoffman–Singleton5017552.00000089.285714−87.285714
cycle \(C_{17}\)1717170.184537212.667543−212.483006
path \(P_{10}\)109∞0.28463068.229405−67.944775
random 3-reg (n = 30, girth 5)304550.154525251.275633−251.121108

4.2 The exhaustive small-order check

The independent reimplementation enumerates all connected simple graphs on \(n\le6\) vertices by edge subsets (1,874 labeled girth-at-least-five graphs), plus all trees, cycles, and unicyclic graphs on 7 vertices (a further 16,812, dominated by the 16,807 labeled 7-vertex trees) — 18,686 labeled graphs in total — and checks the conjecture exactly: the gravity mean is computed as an exact rational number, the characteristic polynomial is exact, and least positive roots are isolated with rational intervals of width \(10^{-18}\). No graph violates the bound. The separate graph-atlas battery independently checks all 35 qualifying graphs through order 7 with the same exact arithmetic.

5. What the proof uses, and why it was not found by search

The 2024 search programs attacked the conjecture spectrally: they computed gravity and spectra for thousands of graphs and found the bound holding everywhere — which is consistent with truth, but gives no proof. The actual argument needs no graph-specific spectral computation. It bounds the gravity mean by a degree sum, bounds every eigenvalue by the trace identity, and lets Reiman's edge bound compare the two. The extremal high-girth graphs that matter for search (the cages) sit far inside the bound, so no search over a finite range of orders could confirm the universal statement — and, the bound being true, none found a counterexample. The conjecture was open because the three lemmas lived in different literatures: gravity matrices (Brewster–Dinneen–Faber), spectral trace identities, and extremal graph theory.

6. Novelty status — stated provisionally

Priority. A targeted search across arXiv, journal indexes, MathOverflow, GitHub, Zenodo, and the Graffiti/Roucairol–Cazenave corpus located no prior resolution of Graffiti 292 and no proof using this reduction. The numbered conjecture remains associated with ambiguous conventions (see the erratum note in the 2024 search paper about the Aouchiche–Hansen versus Written on the Wall definitions of "range"); this report uses the explicit page-80 statement and the gravity normalization reproduced by Brewster–Dinneen–Faber. We therefore report a complete candidate proof that appears new relative to the sources reviewed — not a claim of world-first priority. Independent expert review of (i) the historical statement, (ii) the mean-over-all-\(n^2\)-entries convention, and (iii) prior art is invited before any stronger novelty claim.

7. Reproduction protocol

Everything needed to reproduce this report is in the artifact archive. One command per battery:

python attack_graffiti_292.py          # named graphs + atlas ≤ 7: exact gravity, margins
python verify_symbolic_292.py          # cleared polynomial factorization, endpoint, shift
python verify_small_cases_exact.py     # exact charpoly/root isolation, atlas ≤ 7
python verify_independent_292.py       # from-scratch: 18,686 graphs + analytic bound + cages
python verify_twopath_292.py           # stronger uniform bound (§2.5): cherry-count + Lemma 1, exact
python make_sha256.py                  # regenerate SHA256SUMS.txt

Dependencies: Python 3.13, SymPy 1.14, NetworkX 3.5, NumPy 2.3. Exact arithmetic throughout; floating point is used only for spectra in the named-graph battery, never for the inequality itself.

8. Artifact ledger

ArtifactPurpose
manuscript-graffiti-292.pdftypeset proof (2 pages, XeLaTeX)
manuscript-graffiti-292.texLaTeX source
attack_graffiti_292.py / outputnamed-graph battery
verify_symbolic_292.py / outputsymbolic reduction battery
verify_small_cases_exact.py / outputexact small-case battery
verify_independent_292.py / outputindependent reimplementation (18,686 labeled graphs through order seven)
verify_twopath_292.py / outputstronger uniform bound (§2.5): cherry-count, exact atlas + cages
claim-ledger.jsonclaim-by-claim evidence map
wow-july2004.pdf / page80-detail.txtprimary source scan and OCR of the statement
SHA256SUMS.txtintegrity ledger

Principal hashes at publication time:

ArtifactSHA-256
manuscript (markdown)06f6c3112e3b443678745959dc303a6ed1e2c81dd6177dfb5c7572b1be0de4b6
independent verifier8117c135e9a28be85ecb050aa5a463dfab1786fd3b29ec3bc92ac6ac229e9869
independent verifier output83496f7e53eaffd67248a65f6cba0df783553e0ce74f966de06d2a2728db7611
symbolic verifier output7e621ffac638e0ce26a95b513aa700c496dca056e2dffb12f6cc92f88e839da7
source scan (Written on the Wall)d2c779d2c28418b30ab1b4f84bf7112c0e000bca1f2d6a3c48d0baba78af7733

Acknowledgments

We thank Spanky McDoob (@59thProfile) for the stronger uniform argument recorded in §2.5, and for corrections to the exposition (the asymptotic growth rate of \(L(n)\), the statement of the polynomial-positivity step, the containment-figure wording, and the labeled-graph counts of §§3–4).

References

  1. S. Fajtlowicz, "Written on the Wall," July 2004, p. 80 (conjecture 292); page 52 (gravity matrix definition).
  2. M. Roucairol and T. Cazenave, "Refutation of Spectral Graph Theory Conjectures with Search Algorithms," arXiv:2409.18626, 2024 (open-status table; gravity definition from Brewster–Dinneen–Faber).
  3. T. L. Brewster, M. J. Dinneen, and V. Faber, "A computational attack on the conjectures of Graffiti: new counterexamples and proofs," Discrete Mathematics 147 (1995), 35–55.
  4. S. Jukna, Extremal Combinatorics, §2.2 "Graphs with no 4-cycles" (Reiman-type edge bound).
  5. I. Reiman, "Über ein Problem von K. Zarankiewicz," Acta Math. Acad. Sci. Hungar. 9 (1958), 269–273.
  6. AGNT Labs, "Graffiti 292 reproducibility archive," July 23, 2026, artifact index.
Bottom line. Graffiti 292 is proved under the documented gravity normalization, with a three-line argument, four independent machine-verified batteries, exhaustive exact small-case coverage (18,686 labeled graphs through order seven), and a from-scratch reimplementation that shares no code with the primary verifiers. A stronger, uniform strict bound \(\lambda_+\le n-1