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.
Asked
Active
Viewed 277 times
0
-
Try to prove it for $n = 2$ first. – Sammy Black May 15 '13 at 03:47
2 Answers
2
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.
Lrrr
- 892
-
-
I get the induction part. What I don't get is proving the tree part. – Marcus Pacheco May 15 '13 at 06:33
-
if you get induction part: suppose for every n>m-1 a sequence with your condition is a tree. now remove the node with degree of 1 in your new sequence for m numbers and make one $d_j = d_j - 1$ now you have m-1 numbers and this numbers satisfies your condition; now add a node and connect this node to the node represent $d_j$ – Lrrr May 15 '13 at 10:41
-
0
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.