1
$\begingroup$

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.

  • 0
    possible duplicate of [Condition on degrees for existence of a tree](http://math.stackexchange.com/questions/14100/condition-on-degrees-for-existence-of-a-tree)2012-03-19

3 Answers 3

0

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

2

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.

  • 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.2012-03-16
2

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.

  • 0
    hi @joriki why can't all the degrees be 1? is it because the hypothesis was even so $d_{p+1}$ cant be 1?2018-02-10