A Proof of the Imbalance Conjecture

Abstract

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\{\Delta-k,0\}, \] where $\Delta$ is the maximum degree of $G$. This bound yields all Erd\H{o}s--Gallai inequalities directly; a parity computation completes the proof.