1
$\begingroup$

this is the exercise:

If possible draw a Tree with $15$ vertices having
3 vertices with degree $4$;
4 vertices with degree $3$;
6 vertices with degree $2$;
0 vertices with degree greater than the ones of the above.

This is what I have done:
considering the definition of a tree: with $d_i \ge 1, \,\, \forall \,i \, \, \,1 \le i \le n$

$$\sum_{i=1}^n d_i = 2n-2$$

in the exercise is given the degree of only $13$ vertices, and not $15$ so, $(4,4,4,3,3,3,3,2,2,2,2,2,2,x,y) \\ 36 + x + y = 2(15) - 2 \\ 36 +x+y = 28$
but
$x+y = -8$
i.e. I must add two vertices and (they must have a degree $<4$ as said above) the sum of their degree must result $-8$.
But a tree can't have a vertex with a negative degree by definition.
So it is impossible to draw a tree with the data given in the exercise.

What do you think? Please, can you help me? Thanks!

$\endgroup$
  • $\begingroup$ Your argument looks good to me. $\endgroup$ – quasi Feb 14 '17 at 23:05
  • $\begingroup$ Followup question: With the same degree conditions, what number of total vertices would allow there to be a solution? The answer will suggest that the number $15$ was possibly a typo. $\endgroup$ – quasi Feb 14 '17 at 23:09
  • $\begingroup$ If you follow the further discussion, you'll see that if the number of vertices was specified as $25$ rather than $15$, the condition on the sum of the degrees wouldn't imply that it was impossible. So maybe $15$ was a typo? $\endgroup$ – quasi Feb 15 '17 at 0:23
  • $\begingroup$ @quasi Probably not. $\endgroup$ – JB-Franco Feb 15 '17 at 0:45
  • 1
    $\begingroup$ @JB-Franco I asked a question inspired by this (which led to another question) about the number of trees that might have a given degree sequence... turns out that was a hard question. :-) $\endgroup$ – Joffan Feb 20 '17 at 19:27
1
$\begingroup$

It's well-known that a tree has one fewer edges than the number of nodes, hence your summation. Since there are already at least $(3\cdot 4 + 4\cdot3 + 6\cdot2)/2 = 18$ edges indicated by the degree values already, definitely no such tree on fewer than $19$ vertices is possible, and the negative degree you calculated is an indicator of that.

In fact, since we specify a tree (implicitly a connected graph) and not a forest, any additional nodes would need to have degree no less than $1$ so we'd need an extra $5\cdot2 = 10$ nodes of degree $1$ (plus the two mystery nodes which bump the original base edge count to $19$) to be able to draw a tree with the specified higher-degree nodes:

enter image description here

$\endgroup$
  • $\begingroup$ Wouldn't it require $12$ leaf nodes to make it work? $\endgroup$ – quasi Feb 14 '17 at 23:31
  • $\begingroup$ So, provided there are exactly 12 leaf nodes, the condition on the sum of the degrees is satisfied. Does that automatically imply that such a tree exists? $\endgroup$ – quasi Feb 15 '17 at 0:19
  • $\begingroup$ @ quasi Yes, it does. Trees are too simple to require any more elaborate analysis like Havel-Hakimi $\endgroup$ – Joffan Feb 15 '17 at 0:27
  • $\begingroup$ @JB-Franco: Given the above comments, aren't you glad that the problem specified $15$ vertices rather than $25$? With $15$, you prove it's impossible, and you're done. With $25$, you would need to figure out how to actually draw a tree.satisfying the given conditions. $\endgroup$ – quasi Feb 15 '17 at 0:30
  • $\begingroup$ @quasi not that difficult really... added an example. :-) $\endgroup$ – Joffan Feb 15 '17 at 0:57

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.