PreprintarXiv licencearXiv
A Proof of the Imbalance Conjecture
Abstract
For an edge uv of a finite simple graph G, its imbalance is |dG(u)−dG(v)|, and the imbalance multiset MG consists of the imbalances of all edges of G. Kozerenko and Skochko conjectured that MG 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, ∑e∈ E(G)∖ Amin{k,imbG(e)} ≥ kmax{Δ−k,0}, where Δ is the maximum degree of G. This bound yields all Erdős--Gallai inequalities directly; a parity computation completes the proof.
Related
BibTeX
@misc{schreib2026proof,
title = {{A Proof of the Imbalance Conjecture}},
author = {James Alexander Schreib and Yousof Yavari},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.09191},
eprint = {2608.09191},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.09191},
}
RIS
TY - UNPB
TI - A Proof of the Imbalance Conjecture
AU - James Alexander Schreib
AU - Yousof Yavari
PY - 2026
DA - 2026/09/24
PB - arXiv
DO - 10.48550/arxiv.2608.09191
UR - https://arxiv.org/abs/2608.09191
AB - 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, ∑_e∈ E(G)∖ Amin{k,imb_G(e)} ≥ kmax{Δ−k,0}, where Δ is the maximum degree of G. This bound yields all Erdős--Gallai inequalities directly; a parity computation completes the proof.
ER -