Let $G$ be simple undirected graph and $e=uv\in E(G)$.

The **imbalance** of the edge $e$ is the value $imb(e)=|d(u)-d(v)|$.

Let $M_{G}$ denotes the imbalance sequence (or more correctly, multiset of all edge imbalances) of $G$.

I can prove that if $T$ is a tree, then $M_{T}$ is graphic.

However, in general case it isn't true. See A question on graphic sequences for simple counterexamples.

Based on these I came to the next

Imbalance Conjecture: Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then $M_{G}$ is graphic.

**ADDED 1:** Vova Skochko, a good friend of mine, verified the conjecture for all such graphs with $\leq 9$ vertices.

**ADDED 2:** Recall that the value $Irr(G)=\sum_{e\in E(G)}imb(e)$ is called **irregularity** of $G$.

In light of Erdos-Gallai theorem the Imbalance Conjecture is equivalent to the next statement

Suppose that for all edges $e\in E(G)$ we have $imb(e)>0$. Then for all $E'\subset E(G)$ it holds $$Irr(G)\leq |E'|(|E'|-1)+\sum_{e\notin E'}\left(\min\{{|E'|,imb(e)}\}+imb(e)\right).$$

I wonder does this bound on $Irr(G)$ implies other known bounds on $Irr(G)$ for such graphs?

12more comments