Signature of Connected Line Graphs
Is the difference between the numbers of positive and negative adjacency eigenvalues of every connected line graph at most one? A -vertex witness has signature , and chaining copies gives connected line graphs of signature for every - the signature is unbounded.
- Result
- Disproved (no constant-bound repair of the conjecture is possible)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Construction
- Field
- Spectral graph theory
- Posed by
- Saieed Akbari et al.
- Year posed
- 2026
- Years open
- 0y
- Solved
- 2026-07-30
- Model
- ChatGPT-5.6 Pro, Claude Fable 5
- Vendor
- OpenAI / Anthropic
- Collaborators
- Luke Francis, Trevor Uptain
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 5 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
The 14-vertex witness came from a ChatGPT-assisted search; Claude assisted an independent 48-vertex search and the development of the unbounded family. The authors reproduced everything with separately coded exact-arithmetic audits.
Verification
Exact finite certificates with independent audit implementations; revised arXiv preprint, not yet peer-reviewed.
Source
arXiv:2607.22874 - The signature of connected line graphs is unbounded