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.
Best Answer
Here's a correct proof by induction:
For $p=1$ and $p=2$, the claim is clearly true.
Let the claim be true for some $p\ge2$, and let degrees $d_1,\dotsc,d_p,d_{p+1}$ of $p+1$ vertices be given, with $d_1+\dotso+d_p+d_{p+1}=2(p+1)-2$. Since the degrees cannot all be $1$, we can assume without loss of generality that $d_{p+1}\gt1$. Then the degrees $d_1,\dotso,d_{p-1},d_p+d_{p+1}-2$ satisfy the conditions of the induction hypothesis, so there is a tree with $p$ vertices with these degrees. In that tree, add a $(p+1)$-th vertex, take the $p$-th vertex of degree $d_p+d_{p+1}-2$, remove $d_{p+1}-1$ of its neigbours, attach them to the $(p+1)$-th vertex instead and join the $p$-th and the $(p+1)$-th vertex by an edge. The result is a tree with the desired degrees.