MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 4 down vote accepted

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\}$.

share|cite|improve this answer
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 (…). 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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.