Imbalance conjecture

Importance: Medium ✭✭
Author(s): Kozerenko, Sergiy
Subject: Graph Theory
Recomm. for undergrads: no
Posted by: Sergiy Kozerenko
on: September 24th, 2013
Conjecture   Suppose that for all edges $ e\in E(G) $ we have $ imb(e)>0 $. Then $ M_{G} $ is graphic.

Consider simple undirected graph $ G $ and let $ e=uv\in E(G) $.

The imbalance of the edge $ e $ defined as $ imb(e)=|deg(u)-deg(v)| $.

The multiset of all edge imbalances of $ G $ is denoted by $ M_{G} $.

Note, that conjecture is verified for all such graphs with $ \leq 9 $ vertices.


* indicates original appearance(s) of problem.