I am answering a question for an assignment, but I am not sure if my proof is valid, can someone look at it for me?
the question:
"there is a tree with $p$ vertices. If $d_1, d_2, \dots , d_p$ are positive and $d_1+d_2+d_3+\cdots+d_p = 2p-2$ then there exist a tree with vertices of degrees $d_1, d_2, d_3, .. , d_p$ (HINT: use induction)"
(skipping base case)
induction hypothesis:
assume p = n is true.
i.e. If
d1, d2, .. , dn are positive and d1 + d2 + d3 +..+ dn = 2n - 2.
Then there is a tree with vertices of deg: d1, d2, d3, .. , dn
induction steps:
now look at the case when p = n+1
we have:
d1, d2, .., dn, d(n+1) d1 + d2 + ..+ dn + d(n+1) = 2(n+1) - 2 = 2n.
Comparing this to the p = n case, we see that d(n+1) must be 2.
We must now proof that there exist a tree with vertices of degree: d1, d2, .., dn, d(n+1)
Now from induction hypothesis we know that there is a tree (call it T) with vertices of deg: d1, d2, d3, .., dn. To add a new vertex of degree 2, all we have to do is find a leaf from T, add a new node as a child of that leaf. Now the old leaf will have a degree of d(n+1) (which is 2). Also the new child will have degree of one, which is the same as the old leaf before the new child was added.