4
$\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$
  • $\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 '15 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$ – user2820579 Apr 29 '15 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 '15 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$ – user2820579 Apr 30 '15 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 '18 at 20:08
6
$\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$
  • $\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 '15 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$ – user2820579 Apr 30 '15 at 18:32
  • $\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$ – Leen Droogendijk May 1 '15 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.