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

@rish1602 "**and then remove v from the tree.**" here

 

---

GATE IT 2008,Q77:A binary tree with n gt 1 nodes has n1, n2 and n3 nodes of degree one,two and three

For better Understanding

 

---

This is a very straight forward question. Total edges would for any tree is n-1. Total nodes would be n1+n2+n3. Hence Edges before is n1+n2+n3-1.
Now we delete all edges associated with nodes with degree two and add one edge between it's neighboring nodes. Since a node with with degree 2 will have 2 edges, deleting a node with 2 degree will delete 2*n2 edges and since we add one edge between neighbours, we add n2 number of edges.

So total edges in the end would be = n1+n2+n3-1 - 2n2 + n2 = n1+n3-1

Now since we saw in previous question that n3=n1-2, hence total number of edges in the end will be 2n1-3.

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

Answer 5

Taking a simpler approach.

as we know, n1 = number of leaves = n3 + root + 1 = n3 + 1 

=> n1 = n3 + 2

 

Now 

e = n - 1

   = n1 + n2 + n3 – 1.

after the process, each of two edges adjacent to a degree 2 node will be replaced by 1. For one node, 1 edge decreases. for n2 nodes, n2 edges decreases.

Therefore, new number of edges = e’ = e – n2

= n1 + n2 + n3 – 1 – n2

= n1 + n3 – 1

= n1 + n1 – 2 – 1

= 2*n1 –  3

Option A

 

Answer 6

Here consider in Graph G1 which includes n1=3, n2=1, n3=1 which means number of vertices with one, two and three degrees are given as below. Now we are one node V with degree 2 and removing it so now we'll have n1=3, n2=0, n3=1.

Now calculate initial values from options by putting values of n1,n2 and n3 we get a: 3, b: 5, c: 0 and d: 2 and with final values of n1,n2 and n3 we get options as a: 3, b: 4, c: 1, d:1. So the option where n2's value is used is getting affected so option A is correct.