5
$\begingroup$

I think I'm doing something wrong in the following exercise, but I don't know what it is.

Let the degree sequence of a graph be: $\vec{d}=(d_1,d_2,\dots,d_n)$, where $d_1\ge d_2\ge...\ge d_n\ge 0$, where $d_i$ is the degree of vertex $i$ in the graph. Obviously there are $n$-vertices in the graph.

Show that there's a loopless graph with degree sequence $\vec{d}$ if and only if $\sum_{i=1}^n d_i$ is even and $d_1\leq\sum_{i=2}^n d_i$.


Part $(\Rightarrow)$: In a loopless graph, $d_1\leq m$, where $m=\frac{1}{2}(\sum_{i=1}^nd_i)$. Therefore: $d_1\leq \sum_{i=2}^nd_i$.

Part $(\Leftarrow)$: I have no idea. For example, $n=3$, I know that $d_1\leq d_2+d_3$. I can prove by example that there's a loopless graph, but not for a general case.

$\endgroup$
5
  • $\begingroup$ You're given the ordering, so I don't know that you need to prove it. I find it strange that you're given that "$\sum_{i=1}^n d_i$ is even" when that's required for any graph, but you aren't given any limits on that sum (eg. $n(n-1)$) $\endgroup$
    – Joffan
    Apr 29, 2015 at 21:19
  • $\begingroup$ It's true, the order (I was ignoring this, dammit) is given and by construction, if you like, the sum over the degrees is even, so these two things are checked. The exercise is from Graph Theory, Bondy, 1.1.16. So there can be a loopless graph with these conditions, although I just really need the fact that the sum over the degrees is even. A graph with loops may have degree odd in one of its vertices (for example de graph $V=\{1,2\}$, $E=\{(1,1),(1,2)\}$. What do you think? $\endgroup$ Apr 29, 2015 at 21:52
  • $\begingroup$ Ah... I was thinking we were talking about simple graphs, and took "loops" to mean cycles, and a loopless graph to mean a tree. If not, then the proposition is false I think, or requires a multigraph. $\endgroup$
    – Joffan
    Apr 29, 2015 at 22:08
  • $\begingroup$ The tip given by the authors is: Sufficiency, induction on $\sum_{i=2}^n d_i-d_1$. I cannot find a suitable argument to apply this. $\endgroup$ Apr 30, 2015 at 1:53
  • $\begingroup$ This theorem can also be found in the book "Graph Theory" of Bondy and Murty (2008), p.10, exercise 1.1.16. $\endgroup$
    – SK19
    Mar 19, 2018 at 20:08

1 Answer 1

8
$\begingroup$

The part you are missing can be proved by induction on $\sum d_i$.

The base case $\sum d_i=0$ is realized by $n$ isolated vertices.

Assume $\sum d_i>0$, so at least $d_1\geq1$.

Case 1: $d_1=d_2+\ldots+d_n$. Then take the graph with vertices $v_1,\ldots,v_n$, and $d_i$ edges from $v_1$ to $v_i$ for all $i=2,\ldots,n$.

Case 2: $d_1<d_2+\ldots+d_n$. The difference between the two sides must be at least 2, since the total sum is even. Since $d_1\geq1$ and $d_1$ is the largest value, there must at least be two nonzero values after $d_1$. Now subtract 1 from the two lowest nonzero values and apply the induction hypothesis. In the resulting multigraph add an edge between two vertices whose degrees correspond with the values you reduced in the previous sentence.

$\endgroup$
3
  • $\begingroup$ Nice. You could make the inequality into an equality with the addition of a $2k$ term (justified as even in the same way), $d_1=d_2+\ldots+d_n+2k, k \ge 0$ to give your proof a more familiar induction look. $\endgroup$
    – Joffan
    Apr 30, 2015 at 14:05
  • $\begingroup$ Thanks for the answer. Just one comment that still confuses me (I'm not mathematician but physicist). I will take the case $d_1 < d_2 + \dots + d_n$. Think in the star-loop graph, such that $d_1$ is the center of the star (and therefore has $n-1$ vertices). Now think that every tip of the star has a loop, so the sum over $d_j,\;j\ge 2$ will be $2(n-1)$. In this way, I have created a loop graph with the second part of the proof, apparently contradicting the loopless requierement. $\endgroup$ Apr 30, 2015 at 18:32
  • 1
    $\begingroup$ There is no requirement to prove that ONLY loopless graphs can be constructed satisfying the conditions. You only need to show there is at least one loopless graph satisfying them. $\endgroup$ May 1, 2015 at 4:05

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.