# A question on graphic sequences

Let $G$ be a graph and $d_{G}(u)$ denotes degree of a vertex $u$ in $G$. Consider the next multiset $$M_{G}:=\{|d_{G}(u)-d_{G}(v)|:\ uv\in E(G)\}.$$

Conjecture: $M_{G}$ is graphical for every $G$.

Is it true?

Added: The conjecture is true if $G$ is a tree.

-
Could give the definition of graphical? – Benoît Kloeckner Aug 23 '13 at 11:19
Sorry, a graphic (not "graphical") sequence is a sequence of numbers which can be the degree sequence of some graph. – Sergiy Kozerenko Aug 24 '13 at 10:33

A randomly-generated counterexample is:

which has $$M_G=\{0,0,0,0,0,0,2,2\}$$ which is not graphical. (I marked the vertices with their degrees.)

I should also acknowledge that the above counterexample gives rise to an infinite family of counter-examples:

• Take a connected cubic graph, which exist on $n$ vertices for even $n \geq 4$.
• Delete an edge (one that doesn't disconnect the graph, which must exist, since the graph is not a tree).
• Add pendant vertices to the newly created vertices of degree $2$.

This gives a connected graph with degree sequence $(1,1,3,3,\ldots,3)$ and hence we have $M_G=\{0,0,\ldots,0,2,2\}$.

-
Douglas S. Stones, thanks for your counterexamples! However it turns out that my conjecture is true for trees. I think i can prove it by induction on diameter of G. – Sergiy Kozerenko Aug 24 '13 at 8:31
Yes, I think it's now an interesting question as to which graphs result in a graphical $M_G$. The family above always have $M_G=\{0,0,\ldots,0,2,2\}$ which is very restricted. If I've done my arithmetic right, $\sum M_G$ is even, so it passes the most obvious test. – Douglas S. Stones Aug 24 '13 at 10:07
You mean if $G$ is a tree, then $\sum M_{G}$ is even? BTW, your construction works for every $m$-regular graph, $m>2$. – Sergiy Kozerenko Aug 24 '13 at 10:29
I think it's true for general graphs G. (Ah you're right... they'll end up with {0,..,0,m-1,m-1}.) – Douglas S. Stones Aug 24 '13 at 10:32
Firstly, the value $|d(u)-d(v)|$ is called imbalance of the edge $uv\in E(G)$, see (mathoverflow.net/questions/134513/…). Also, inspired by your series of counterexamples I came to the next conjecture: if for all $u,v\in V(G)$ with $uv\in E(G)$ it holds that $d(u)\neq d(v)$, then $M_{G}$ is graphic. It would be interesting to see a counterexample to this :) Oh, and yes, $\sum M_{G}$ is always even. – Sergiy Kozerenko Aug 24 '13 at 15:01