A Proof of the Imbalance Conjecture
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.09191
curl -X POST /api/v1/records/arxiv/2608.09191/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.09191/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'