# A proof of Graffiti 292

**Status:** candidate proof package, independently reproducible from the accompanying scripts.  
**Date:** 23 July 2026.

## Abstract

Let \(G\) be a connected simple graph of order \(n\) and girth at least five. The gravity matrix is

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

and its mean is taken over all \(n^2\) entries. Graffiti 292 states that the least positive adjacency eigenvalue of \(G\) is at most \(n/\operatorname{mean}(\operatorname{Gr})\). We prove the conjecture by combining a degree-sum upper bound for mean gravity, the trace bound \(\lambda^2\le 2m\), and the standard extremal edge bound for graphs of girth at least five. Orders \(n\le 6\) are dispatched directly.

## The conjecture

For a graph \(G\), let \(\lambda_+(G)\) denote its least positive adjacency eigenvalue. Graffiti 292 is:

> If \(G\) has girth at least five, then
> \[
> \lambda_+(G)\le \frac{n}{\overline{\operatorname{Gr}}},
> \]
> where \(\overline{\operatorname{Gr}}\) is the mean of all entries of the gravity matrix.

The statement is read directly from page 80 of *Written on the Wall*; the gravity definition is the one reproduced by Roucairol and Cazenave from Brewster--Dinneen--Faber.

## Lemma 1: a lower bound for \(n/\overline{\operatorname{Gr}}\)

Let \(m\) be the number of edges. Since \(d(u,v)\ge 1\) for \(u\ne v\),

\[
\begin{aligned}
\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{1}{n^2(n-1)}\left(\sum_u d(u)\right)^2\\
&=\frac{4m^2}{n^2(n-1)}.
\end{aligned}
\]

Therefore

\[
\frac{n}{\overline{\operatorname{Gr}}}\ge \frac{(n-1)n^3}{4m^2}. \tag{1}
\]

## Lemma 2: every adjacency eigenvalue is at most \(\sqrt{2m}\) in absolute value

If \(\lambda_1,\ldots,\lambda_n\) are the adjacency eigenvalues, then

\[
\sum_{i=1}^n\lambda_i^2=\operatorname{tr}(A^2)=2m.
\]

Hence each \(|\lambda_i|\le \sqrt{2m}\), and in particular

\[
\lambda_+(G)\le \sqrt{2m}. \tag{2}
\]

## Lemma 3: edge bound for girth at least five

A graph of order \(n\) containing no triangles or four-cycles satisfies

\[
m\le B(n):=\frac n4\left(1+\sqrt{4n-3}\right). \tag{3}
\]

This is the standard Reiman-type extremal bound for \(\{C_3,C_4\}\)-free graphs.

## Main theorem

**Theorem.** Graffiti 292 is true.

**Proof.** Suppose first that \(n\ge 7\). Put

\[
t=\sqrt{4n-3},
\qquad
n=\frac{t^2+3}{4},
\qquad t\ge5.
\]

The function \(m\mapsto (n-1)n^3/(4m^2)\) is decreasing and \(m\mapsto\sqrt{2m}\) is increasing. Thus, using (3), it suffices to prove

\[
\frac{(n-1)n^3}{4B(n)^2}\ge \sqrt{2B(n)}. \tag{4}
\]

Both sides are positive. Squaring (4), substituting \(n=(t^2+3)/4\), and clearing positive denominators reduces the claim to positivity of

\[
P(t)=2(t+1)^2\left(t^4-4t^3-2t^2-12t+1\right).
\]

Write \(t=u+5\) with \(u\ge0\). Direct expansion gives

\[
P(u+5)=2u^6+56u^5+632u^4+3600u^3+10400u^2+12480u+1152>0.
\]

Therefore (4) holds. Combining (1), (4), (3), and (2),

\[
\frac{n}{\overline{\operatorname{Gr}}}
\ge \frac{(n-1)n^3}{4m^2}
\ge \sqrt{2m}
\ge \lambda_+(G).
\]

It remains to check \(n\le6\). Connected graphs of girth at least five on at most six vertices are trees, \(C_5\), \(C_6\), or unicyclic graphs obtained from \(C_5\) by attaching one leaf. These finitely many graphs can be checked directly; the accompanying exhaustive graph-atlas computation verifies all connected simple graphs of order at most seven satisfying the girth condition. Alternatively, the small cases may be enumerated by hand from the preceding classification. This completes the proof. \(\square\)

## Reproduction

Run:

<pre><code>python attack_graffiti_292.py
python verify_symbolic_292.py
</code></pre>

The first script checks exact gravity means and numerical spectra on named graphs, random regular graphs, and every connected graph in the NetworkX graph atlas satisfying the girth condition. The second script verifies the symbolic factorization and positivity certificate.

## Source notes

1. S. Fajtlowicz, *Written on the Wall*, July 2004, p. 80: conjecture 292.
2. M. Roucairol and T. Cazenave, *Refutation of Spectral Graph Theory Conjectures with Search Algorithms*, arXiv:2409.18626: gravity-matrix definition and 2024 open-status table.
3. The exact page scan, OCR output, scripts, and run logs are included in this package.