Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
possible duplicate of Condition on degrees for existence of a tree –  Gerry Myerson Mar 19 '12 at 9:55
add comment

3 Answers

up vote 1 down vote accepted

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.

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
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
1  
@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
1  
@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
show 1 more comment

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}.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.