{"id":"arxiv/2608.09191","url":"https://arxiv.org/abs/2608.09191","tags":["math.CO","cs.DM"],"score":0,"title":"A Proof of the Imbalance Conjecture","domain":"math.CO","source":"arxiv","authors":["James Alexander Schreib","Yousof Yavari"],"reviews":0,"subject":"math.CO","summary":"For an edge $uv$ of a finite simple graph $G$, its imbalance is $|d_G(u)-d_G(v)|$, and the imbalance multiset $M_G$ consists of the imbalances of all edges of $G$. Kozerenko and Skochko conjectured that $M_G$ is graphic whenever every edge has positive imbalance. We prove this conjecture. The main ingredient is the following capacity bound: for every set $A$ of $k$ edges, \\[ \\sum_{e\\in E(G)\\setminus A}\\min\\{k,\\operatorname{imb}_G(e)\\} \\ge k\\max\\{Δ-k,0\\}, \\] where $Δ$ is the maximum degree of $G$. This bound yields all Erdős--Gallai inequalities directly; a parity computation completes the…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-10","reactions":{}}