here is the proof:
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 02) 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)
or there is only one line coming to it (it will be the end of the tree and the degree is 1)
There is another poof : The number of degree 1 vertices is 2 more than the number of degree 3 vertices.
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
ok give me a sec
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 binomialtree 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 twostep 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 verticeswill 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
Hi are you still there