# Prove the existence of a Tree of 15 vertices with some vertices degree given

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!

• Your argument looks good to me. – quasi Feb 14 '17 at 23:05
• 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. – quasi Feb 14 '17 at 23:09
• 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? – quasi Feb 15 '17 at 0:23
• @quasi Probably not. – JB-Franco Feb 15 '17 at 0:45
• @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. :-) – Joffan Feb 20 '17 at 19:27

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:
• Wouldn't it require $12$ leaf nodes to make it work? – quasi Feb 14 '17 at 23:31
• @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. – quasi Feb 15 '17 at 0:30