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!
Best Answer
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: