Graffiti Conjecture 284

If a finite graph has girth at least five, must its minimum dual degree satisfy $\delta^*(G) \le -\partial_n(G)$ , where $\partial_n(G)$ is the smallest eigenvalue of its distance matrix? The Hoffman-Singleton graph violates it: dual degree $7$ against eigenvalue bound $4$ .

Result: Disproved
Status: Resolved
AI contribution: AI-discovered
Method: Construction
Field: Spectral graph theory
Posed by: Graffiti (Siemion Fajtlowicz's program)
Year posed: 1996
Years open: 30y
Solved: 2026-07-22
Model: Grok 4.5 Medium (Capy build)
Vendor: xAI
Collaborators: —
Verification: Unreviewed
Publication: Announced
Significance: 5 / 100
Disclosed cost: —
Wikipedia: No dedicated article

What the AI did

The Capy agent running Grok 4.5 Medium identified the Hoffman-Singleton graph as a counterexample; the certificate was reproduced independently under adversarial review.

Verification

Publicly posted exact certificate on a classical, independently checkable graph (Hoffman-Singleton); no formal writeup yet.

Source

Public certificate thread (X)

Graffiti Conjecture 284

What the AI did

Verification

Source

Discussion