How JustAnswer Works:
• Ask an Expert
• Get a Professional Answer
• 100% Satisfaction Guarantee
Ask David Your Own Question
David, Tutor
Category: Homework
Satisfied Customers: 2310
Experience:  PhD in Theoretical Physics
394177
Type Your Homework Question Here...
David is online now

# A binary tree can be recursively defined as follows. A single

This answer was rated:
A binary tree can be recursively defined as follows.
A single vertex is a binary tree. (This single vertex is the root of this binary tree.)
If T1 and T2 are binary trees, then so is the result of the following construction.
– Create a new vertex. (This vertex will become the root of the new binary tree.)
– Add an edge between this new root vertex and the roots of T1 and T2.
Prove the following for all binary trees:
• Root vertices either have degree 0 or 2 and are the only vertices with these degrees.
The number of degree 1 vertices is 2 more than the number of degree 3 vertices.
(Hint: It will be simpler to combine the two properties in a single proof.)

David :

here is the proof:

David :

First we prove that Root vertices either have degree 0 or 2.
Only two possibilities that we have.
1) if the vertex is the tree itself (just a point) then the degree is 0
2) if the vertex is constructed by joining to other two trees (hence the name binary)
in this case the degree is 2.
all other vertices do not have 0 or 2 degree, because it the vertex is NOT root, then
it there is a line coming to it and two lines going out (so the degree is 3)

David :

or

David :

or there is only one line coming to it (it will be the end of the tree and the degree is 1)

Customer:

There is another poof : The number of degree 1 vertices is 2 more than the number of degree 3 vertices.

Customer:

In this question need to proof two statement: a)The number of degree 1 vertices is 2 more than the number of degree 3 vertices b) The number of degree 1 vertices is 2 more than the number of degree 3 vertices

David :

ok give me a sec

Customer:

thx

David :

Here is the proof:
a) Above I've argued that vertices other than root can be of degree 1 or 3. and any vertex of degree 1 has a pair
that is joined to a vertex of degree 3 (by construction) and for the base case of a two step binomial
tree we have 4 vertices of degree 3 ans 2 vertices of degree 2.
Now, for any number of steps binomial tree we can break it into components of two
step binomial tree (by construction) by joining the root vertices to a new vertices.
but in this case the number of degree 3 in each 2 step binomial tree wil increase by 1, because the
root vertices becomes degree 3 vertex. so we can go by induction here:
If for tree T1 and tree T2 the numbers of degree vertices are n3 and m3 and the
degree 1 vertices were n3+2 and m3+2 correspondingly,then upon joining T1 and T2
the degree 1 vertices will be n3+2+m3+2 = n3+m3+4. But the number of degree 3 vertices
will be n2+m3+2 (note I add 2 because the root vertices of T1 and T2 now become degree 3 vertices)
as you see n3+m3+4 is 2 more than n3+m3+2, as expected.
DONE

Customer:

Hi are you still there

David and 3 other Homework Specialists are ready to help you
Customer: replied 4 years ago.
close it
Ok.