Imbalance Conjecture

Definitions and mathematical statement

Shared notation.

$\mathbb N=\{1,2,\ldots\}$, and $\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$ denote the integers, rationals, reals and complex numbers. Any other conventions are specified locally.

For a finite simple undirected graph $G$, write $d_G(v)$ for the number of neighbors of a vertex $v$. The imbalance of an edge $e=uv$ is $i_G(e)=|d_G(u)-d_G(v)|$. Its imbalance multiset is $M_G=\{\!\{i_G(e):e\in E(G)\}\!\}$, where repeated values are counted once for each edge. A finite multiset is graphic when it is the multiset of vertex degrees of some finite simple graph.

Statement recorded in the supplied source.

For every finite simple graph $G$ such that $i_G(e)\ge1$ for every edge $e$, is $M_G$ graphic? Equivalently, writing $m=|E(G)|$, must there exist a simple graph $H$ with $m$ vertices and a bijection $\psi:E(G)\to V(H)$ such that \[ d_H(\psi(e))=i_G(e)\qquad(e\in E(G))? \] If $G$ has no edges, the empty graph $H$ realizes the empty multiset. [S2]

Short English statement

If every edge joins vertices of different degrees, must the edge degree-differences be the vertex degrees of some simple graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 1438 (GRAPH-051). CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 James Alexander Schreib and Yousof Yavari, A Proof of the Imbalance Conjecture, arXiv:2608.09191v3 (2026), Section 1 and Theorem 1.1. https://arxiv.org/pdf/2608.09191v3.