2026-08-11
A proof attributed to GPT-5.6 settles the 2014 Imbalance Conjecture: in any graph where every edge joins vertices of different degree, the multiset of edge imbalances is itself the degree sequence of some graph.
Albertson (1997) measured how irregular a graph is by the sum of all its edge imbalances, where an edge's imbalance is the absolute difference of its two endpoint degrees. Kozerenko and Skochko (2014) shifted focus from the sum to the multiset MG of individual edge imbalances and conjectured: if every edge has positive imbalance (no edge joins equal-degree vertices), then MG is graphic, meaning it can be the degree sequence of some graph. Kozerenko and Serdiuk (2023) verified this computationally for all graphs up to 12 vertices, but a general proof was missing. This paper supplies it.
The target is to satisfy the Erdős–Gallai theorem, which says a nonincreasing integer list is the degree sequence of a simple graph iff its sum is even and it meets one inequality per prefix k (the sum of the k largest entries is at most k(k−1) plus Σ min{k, xᵢ} over the rest). The whole task reduces to: ordering MG as x₁≥…≥xm, prove every Erdős–Gallai inequality holds, plus an even sum.
The main new tool is Lemma 3.1 (truncated imbalance bound): if at least k edges have imbalance ≥ k, then Tk = Σe min{k, δ(e)} ≥ k(D+1), where D is the maximum imbalance. Its proof deletes the high-degree endpoint of a maximum-imbalance edge, splits the remaining edges into those incident to that vertex versus the rest, bounds each pile, and works two cases h≥k and h<k. This lemma is the only place that needs real work; the rest is application.
The main theorem inducts on k in two cases. If xk ≥ k (the top k imbalances are all ≥ k), the lemma gives Tk ≥ k(D+1), and since xᵢ ≤ D this yields the Erdős–Gallai inequality. If xk < k, then min{k, xᵢ}=xᵢ from position k onward, giving the recurrence Φk − Φ{k−1} = 2(k−1−xk) ≥ 0. A final parity check: |d(u)−d(v)| ≡ d(u)+d(v) (mod 2), so summing over all edges gives Σ δ(e) ≡ Σv d(v)², which is ≡ Σv d(v) = 2|E| ≡ 0, hence the sum is even. Erdős–Gallai is fully met, so MG is graphic.
Unlike the counterexample paper, this is a pure analytic proof with no machine-verifiable computation. The argument chain was not re-derived line by line; the writeup was revised by the author from a GPT-5.6 draft and checked by Eric Hou.
The single result is Theorem 1.1: under the positive-imbalance hypothesis, MG is graphic. The Imbalance Conjecture holds. No benchmark.
This is the sibling of the counterexample paper: same author, same tool (GPT-5.6 Sol Max), same week. The difference is direction, since this one is a positive proof and that one a counterexample. Taken together they show a fuller picture of an LLM's output on open math: it can both refute a conjecture and supply a complete proof. For graph theory itself, this closes the imbalance-sequence line, connecting the 2014 conjecture and the 2023 computational check to the general case.