A Proof of the Imbalance Conjecture
2026-08-10 • Discrete Mathematics
Discrete Mathematics
AI summaryⓘ
The authors studied a property of graphs related to how different the number of connections (degrees) are between pairs of connected nodes. Kozerenko and Skochko had a guess (a conjecture) that if every connection shows some difference in degrees, then these differences can form a valid sequence representing a graph. The authors proved this guess is true by developing a mathematical inequality about sums involving these differences. Their work used known results (Erdos-Gallai inequalities) and some parity calculations to finalize the proof.
graph theorydegree of a vertexedge imbalancegraphic sequenceErdos-Gallai inequalitiesparityfinite simple graphmultisetgraph realization
Authors
Yousof Yavari
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 a lower bound for the truncated sum $\sum_{e\in E(G)}\min\{k,\operatorname{imb}_G(e)\}$ when at least $k$ edges have imbalance at least $k$. This bound yields all Erdos-Gallai inequalities for the nonincreasing list of edge imbalances; a parity computation then completes the proof.