Existence of -Edge-Balanced Graphs for
A graph on vertices with edges is -edge-balanced if every graph on vertices with edges is contained in exactly the same number of subgraphs of isomorphic to . Infinite families were known for , but no example was known for any . Resolved in both directions: -edge-balanced graphs exist, and no nontrivial -edge-balanced graphs exist for .
- Result
- Proved
- Status
- Resolved
- AI contribution
- AI-assisted
- Method
- Computation
- Field
- Design theory
- Posed by
- open in the design theory literature
- Year posed
- —
- Years open
- —
- Solved
- 2026-05-16
- Model
- ChatGPT
- Vendor
- OpenAI
- Collaborators
- Yeow Meng Chee
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What the AI did
Tooling rather than mathematics: the simulated annealing search was implemented in C++ with the code developed with the assistance of ChatGPT. The search then found zero-score graphs for 11 parameter sets including the ten smallest. The arithmetic conditions on the parameters and the nonexistence proof for are the author's.
Verification
The examples are explicit graphs, published with source code, and each candidate had its subgraph count profile recomputed from scratch as an independent check. That makes the existence half verifiable by anyone who reruns the count. arXiv preprint, not peer-reviewed.