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.8k 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.