Let G be a finite simple undirected graph with vertex set V(G) and edge set E(G), and for u∈ V(G) let deg(u) denote the number of neighbours of u in G. For an edge e=uv∈ E(G) define its imbalance by imb(e)=|deg(u)-deg(v)|, and let M_G be the multiset of edge imbalances of G, i.e. the multiset imb(e) : e∈ E(G) of cardinality |E(G)|, each edge contributing one element. Call a finite multiset d_1,d_2,…,d_n of non-negative integers graphic if there is a finite simple graph H with vertices w_1,w_2,…,w_n such that deg_H(w_i)=d_i for every i∈1,…,n (no loops or multiple edges are permitted in H). Then for every finite simple graph G with the property that imb(e)>0 qquadfor all e∈ E(G), that is, no edge of G joins two vertices of equal degree, the multiset M_G is graphic.

imbalance conjecture

About 13 years old · traced to 2013

Let $G$ be a finite simple undirected graph with vertex set $V(G)$ and edge set $E(G)$ , and for $u\in V(G)$ let $\deg(u)$ denote the number of neighbours of $u$ in $G$ . For an edge $e=uv\in E(G)$ define its imbalance by

\mathrm{imb}(e)=|\deg(u)-\deg(v)|,

and let $M_G$ be the multiset of edge imbalances of $G$ , i.e. the multiset $\{\mathrm{imb}(e)\ :\ e\in E(G)\}$ of cardinality $|E(G)|$ , each edge contributing one element.

Call a finite multiset $\{d_1,d_2,\dots,d_n\}$ of non-negative integers graphic if there is a finite simple graph $H$ with vertices $w_1,w_2,\dots,w_n$ such that $\deg_H(w_i)=d_i$ for every $i\in\{1,\dots,n\}$ (no loops or multiple edges are permitted in $H$ ).

Then for every finite simple graph $G$ with the property that

\mathrm{imb}(e)>0\qquad\text{for all } e\in E(G),

that is, no edge of $G$ joins two vertices of equal degree, the multiset $M_G$ is graphic.

References

Primary source

Wikipedia

Additional references

Wikipedia, Imbalance conjecture, the article this problem comes from.

graph-theory unsolved-problem

Posted 1 month ago · edited 1 week ago

Progress summary

Refreshed 1 week ago

Claimed solved

A preprint and a later exposition claim that the conjecture has been proved, but independent confirmation is not recorded.

Kozerenko and Skochko formulated the conjecture in 2014: whenever every edge joins vertices of different degrees, the multiset of edge degree differences should itself be a degree multiset.

Known results

Computationally verified for graphs with at most $12$ vertices.
Proved for trees and for certain split graphs.
Established for complete extensions of paths, cycles, and complete graphs.

August 2026 claimed proof

Yousof Yavari’s preprint claims a complete proof via a capacity bound, the Erdős–Gallai inequalities, and a parity check. It reports a merged proof developed with OpenAI’s named models and links a Lean 4 formalization. An August 18 exposition also presents the theorem as proved, but these claims remain unverified.

Current status (as of September 2026): A complete proof and a Lean formalization are publicly claimed, but independent mathematical or formal verification is not recorded.

Sources

No solutions have been posted yet.