61 votes 61 votes A binary tree with $n > 1$ nodes has $n_1$, $n_2$ and $n_3$ nodes of degree one, two and three respectively. 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? $2 * n_1- 3$ $n_2 + 2 * n_1 - 2$ $n_3 - n_2$ $n_2+ n_1- 2$ DS gateit-2008 data-structures binary-tree normal + – Ishrat Jahan asked Oct 29, 2014 edited Dec 26, 2017 by kenzou Ishrat Jahan 14.6k views answer comment Share Follow See all 7 Comments See all 7 7 Comments reply Show 4 previous comments Subhajit Panday commented Jun 8, 2020 i edited by Subhajit Panday Jun 8, 2020 reply Follow Share 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 2 votes 2 votes rish1602 commented Dec 13, 2021 reply Follow Share 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 ? 2 votes 2 votes kickassakash commented Sep 4, 2023 reply Follow Share if anyone is wondering bout how @Sumit1311 got this equation n3 = n1- 2 (best answer in this section) then here is the proof 2 votes 2 votes Please log in or register to add a comment.
Best answer 89 votes 89 votes 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$ Sumit1311 answered Jan 28, 2016 selected Jun 29, 2019 by Arjun Sumit1311 comment Share Follow See all 15 Comments See all 15 15 Comments reply Show 12 previous comments arpit_18 commented Nov 12, 2020 reply Follow Share 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. 0 votes 0 votes Kiyoshi commented Apr 27, 2021 reply Follow Share @arpit_18 given in question… has n1, n2 and n3 nodes of degree one, two and three respectively. 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) 0 votes 0 votes samarpita commented Jul 1, 2022 reply Follow Share “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; } 1 votes 1 votes Please log in or register to add a comment.
46 votes 46 votes From the above tree, we will get the tree below Now, check with the options we will get $(A)$ as the answer. Shreyans Dhankhar answered Oct 29, 2014 edited Jun 28, 2019 by Lakshman Bhaiya Shreyans Dhankhar comment Share Follow See all 10 Comments See all 10 10 Comments reply Show 7 previous comments talha hashim commented Aug 6, 2018 reply Follow Share this is a nice problem 0 votes 0 votes Chaitrasj commented Nov 14, 2018 reply Follow Share Hi I tried with this graph but none of the options are matching. Can anyone please tell where I am doing wrong. Thanks 0 votes 0 votes neel19 commented Jan 30, 2021 reply Follow Share You forgot to remove the upper node which still has degree 2. 0 votes 0 votes Please log in or register to add a comment.
5 votes 5 votes 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 chandra sai answered Jul 5, 2019 chandra sai comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes 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$ . HeadShot answered Nov 11, 2018 HeadShot comment Share Follow See all 0 reply Please log in or register to add a comment.