The Imbalance Conjecture
The imbalance of an edge uv of a finite simple graph is the absolute difference of the degrees of u and v. Kozerenko and Skochko conjectured that the multiset of all edge imbalances is graphic - realizable as the degree sequence of some graph - whenever every edge has positive imbalance. Proved.
- Result
- Proved(see note)
- Status
- Resolved
- AI contribution
- AI-discovered
- Method
- Argument
- Field
- Graph theory
- Posed by
- Sergiy Kozerenko, Volodymyr Skochko
- Year posed
- 2013
- Years open
- 13y
- Solved
- 2026-08-10
- Model
- GPT-5.6 Sol Max
- Vendor
- OpenAI
- Collaborators
- Yousof Yavari
- Verification
- Unreviewed
- Publication
- Preprint
- Significance
- 10 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
The key step is a lower bound on the truncated imbalance sum, which yields every Erdos-Gallai inequality for the sorted imbalance list; a parity computation finishes it.
What the AI did
The generative-AI disclosure says the model was asked to solve the problem outright: "The proof presented in this manuscript was generated using OpenAI's GPT-5.6 Sol with the max reasoning setting (\"GPT-5.6 Sol Max\") after Yousof Yavari prompted the model to solve the question addressed in this manuscript. Yousof Yavari subsequently revised and edited the proof, added further details, and clarified its exposition."
Verification
A preprint days old. The author credits Eric Hou with independently verifying the proof, which is a second reader rather than the kind of review that moves an entry up the ladder.
Source
- PaperarXiv