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

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