Prove there is a tree with $n$ vertices having degrees $d_1, d_2....d_n$

Question

For $n ≥ 2$ suppose $d_1, d_2,....d_n$ are positive integers with sum $2n - 2$. Prove there is a tree with n vertices having degrees $d_1, d_2....d_n$. I'm at a loss on this one. I'm sure it's pretty simple but I just can't get it.

Answer 1

you can use induction : it's obvious for n = 2; prove that there is at lease an $a_i = 1$ in this sequence and also there is at least one $a_i\geq 2$ and use this to fact.

P.S: since it's homework I would rather not to solve the problem but just give hints.

Answer 2

Proceed along the following lines.

• First show that there exists one $d_i$ such that $d_i = 1$. Why is this true? What will happen if all the $d_j$'s are greater than $1$?
• Remove this vertex. What happens to the sum $\sum_{j \neq i} d_j$?
• Now induction to the rescue.