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.

  • 1
    $\begingroup$ Could give the definition of graphical? $\endgroup$ Aug 23, 2013 at 11:19
  • 1
    $\begingroup$ Sorry, a graphic (not "graphical") sequence is a sequence of numbers which can be the degree sequence of some graph. $\endgroup$ Aug 24, 2013 at 10:33

1 Answer 1


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

  • 1
    $\begingroup$ 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. $\endgroup$ Aug 24, 2013 at 8:31
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 24, 2013 at 10:07
  • 1
    $\begingroup$ You mean if $G$ is a tree, then $\sum M_{G}$ is even? BTW, your construction works for every $m$-regular graph, $m>2$. $\endgroup$ Aug 24, 2013 at 10:29
  • 1
    $\begingroup$ I think it's true for general graphs G. (Ah you're right... they'll end up with {0,..,0,m-1,m-1}.) $\endgroup$ Aug 24, 2013 at 10:32
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 24, 2013 at 15:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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