GATE IT 2008 | Question: 77

Question

A binary tree with $n > 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respec­tively. The degree of a node is defined as the number of its neighbours.

Starting with the above tree, while there remains a node $v$ of degree two in the tree, add an edge between the two neighbours of $v$ and then remove $v$ from the tree. How many edges will remain at the end of the process?

• A. $2 * n_1- 3$
• B. $n_2 + 2 * n_1 - 2$
• C. $n_3 - n_2$
• D. $n_2+ n_1- 2$

Comments

Easiest Approach -

Following the process ( removing deg 2 vertices and adding edge ) will eat up all the degree 2 (n2) vertices without affecting degrees of other vertices ! Remaining edges =(n1+n3)-1------(i) ( |E|=n-1 for a tree ) ! Since this is not in option , think of manipulating the equation !!

Apply Sum Of degree theorem on the tree ( unmodified tree ) =n1 + n2*2 + n3*3= 2|E|  (|E|= n1 + n2 + n3 -1)

=>n1-n3=2 ----(ii)

put (ii) in (i)-------Remaining Edges= 2*n1-3 ( OPTION A)

 

PS- This would not have been true if definition of degree would have been ,deg(node)=no of children  

---

The question states “while there remains a node of degree two in the tree, add an edge between the two neighbours”

Where is it mentioned to remove all nodes of degree 2 ?

---

if anyone is  wondering bout how @Sumit1311 got this equation n3 = n1- 2 (best answer in this section) then here is the proof

 

Answer 1

Initially, $n_1*1+n_2*2+n_3*3=2(n_1+n_2+n_3-1)   \implies  n_3=n_1-2$

Now we have removed all $2$ degree nodes, so number of edges in final graph is $n_1+n_3-1.$

Put $n_3=n_1-2,$ we get

Number of edges $=2*n_1-3$

Comments

Now we have removed all 22 degree nodes, so number of edges in final graph is n1+n3−1

How did this expression came? Please explain somebody.

---

@arpit_18

given in question…

has n1, n2 and n3 nodes of degree one, two and three respec­tively.

According to question total number of nodes is (n1+n2+n3) and now  we are removing 2 degree nodes that means n2 . finally left with n1 and n3.

   total number of nodes = (n1+n3)

Now if tree contains n nodes then it have (n-1) edges.

So, number of edges = (n1+n3-1) 

 

---

“while there remains a node v of degree 2” it means

while( there is a node of degree 2)

{

   add an edge between the two neighbours of v;

  then remove v from the tree;

}

Answer 2

From the above tree, we will get the tree below 

Now, check with the options we will get $(A)$ as the answer.

Comments

this is a nice problem

---

Hi I tried with this graph but none of the options are matching. Can anyone please tell where I am doing wrong. Thanks

---

You forgot to remove the upper node which still has degree 2.

 

Answer 3

Another method:

Sum of degrees: n1+2*n2+3*n3

now number of edges =  (n1+2*n2+3*n3)/2

now all 2 degree nodes were removed ... by doing this degrees of remaining vertices will not affect. as we are forming an edge between neighbouring vertices.

hence number of edges= (n1+2*n2+3*n3-2*n2)/2 =  (n1+3*n3)/2

now replace n3 = n1-2 (from first linked question)

=>(n1+3(n1-2)) / 2

=>2n1-3

Answer 4

May be we can eliminate b, c ,d .

By applying procedure given in a question, there will not be any node with degree 2 left  i.e  $n_2$ , only option A doesn't have   $n_2$ .