# Sufficient conditions on degrees of vertices for existence of a tree

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.

-
possible duplicate of Condition on degrees for existence of a tree – Gerry Myerson Mar 19 '12 at 9:55

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.

-
Thanks for the help, but I don't understand the part "then the degree d1, ... d(p+1) -2 satisfy the conditions of the induction hypothesis" are you implying that d(p+1) = 2 because I did that before and Aryabhata told me I couldnt do that – user308553 Mar 16 '12 at 9:15
No, I'm not implying that. If $d_1+\dotso+d_p+d_{p+1}=2(p+1)-2=2p$, then $d_1+\dotso+d_{p-1}+(d_p+d_{p+1}-2)=2p-2$, which is the condition of the induction hypothesis. There's no assumption on $d_{p+1}$ involved, other than that $d_{p+1}\gt1$, since otherwise $d_p+d_{p+1}-2$ might not be positive; and I explained why we can make that assumption. (That's why I treated $p=2$ separately, since in that case both degrees are $1$ and this wouldn't work.) – joriki Mar 16 '12 at 9:21
ohh I think I get it now, thanks a lot!!! – user308553 Mar 16 '12 at 9:22
You're welcome. – joriki Mar 16 '12 at 9:22

You can just compare the terms like that.

The induction hypothesis is: For any $d_1, d_2, \dots d_n$ such that

$$d_1 + d_2 + \dots + d_n = 2n-2$$

there is a tree with those degrees.

The statement you wish to prove is

For every $e_1, e_2, \dots e_{n+1}$ such that

$$e_1 + e_2 + \dots + e_{n+1} = 2(n+1) - 2$$

there is a tree with those degrees.

Note that these need not be the same as the $d_i$. In fact the $d_i$ and $e_i$ refer to a whole set of them and not just a single sequence. The $e_i$ are arbitrary and you cannot assume any connection with the $d_i$.

In short, your proof is incorrect.

-
if di and ei have no connection to di. How do we use the induction hypothesis. And also we can't say that the new added vertex is of degree 2? – user308553 Mar 16 '12 at 2:30
@user308553: The term 'new added vertex' is meaningless. All you are given is a set of $n+1$ numbers which add up to $2(n+1) - 2$. You haven't yet associated that with a tree yet! The induction hypothesis is if there are $n$ numbers which add to $2n-2$, then there is a tree. You can use it however you want. – Aryabhata Mar 16 '12 at 2:35
Oh you are right, I didnt see that. thanks, I will spend more time thinking on this. I actually have one more question. I know this is incorrect but I can't explain why: We all know that for a tree, sum of deg(vi) = n1 + 2*n2 + 3*n3 + ... = 2(p-1). (n1 = the number of vertex of degree 1, n2 = the number of vertex of degree 2) Doesn't that already kinda proof this question? – user308553 Mar 16 '12 at 2:44
@user308553: No, it does not. You are asked to prove the converse. For example: If an animal is a dog, it has a tail. This is true. But if an animal has a tail, it is not necessarily true that it is a dog. You statement is: If there is a tree with degrees $d_1, d_2, \dots d_n$ then the sum of $d_n$ is $2n-2$. The problem asks you to prove the converse. – Aryabhata Mar 16 '12 at 2:46
o yea. Thanks!! – user308553 Mar 16 '12 at 2:48

Others have given nice answers, but I wanted to mention that, conceptually, the main point is that every tree has a leaf. In this sense, the OP is on the right track. I would have proved it like this, which is similar to what the OP wanted to do.

Since the $d_i$ sum to $2n-2$, if $n>2$, we can assume that $d_1=1$ and $d_2>1$. In this case, the sequence $d_2 - 1, d_3,\ldots, d_{n-1}$ will satisfy the induction hypothesis on $n-1$ vertices. It is now obvious how to construct the tree: start with the one from the IH on vertices $2,3,\ldots, n$ and add the edge {1,2}.

-