0 votes 0 votes if m=4 and n=6 (complete graph) option B says removal of mC2-n+2 = 6-6+2=2 edges. but it needs 3 edges to make the graph disconnected. how B is answer? Graph Theory made-easy-test-series engineering-mathematics discrete-mathematics graph-theory graph-connectivity + – Anusha Motamarri asked Dec 8, 2016 recategorized Mar 4, 2019 by akash.dinkar12 Anusha Motamarri 819 views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply Prabhanjan_1 commented Dec 8, 2016 reply Follow Share given in the question always ; So what if n=4 and m=4 connected graph.?? 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share yeah given "always" so even if there is one example which contradicts the given answer,that is not gonna be correct 0 votes 0 votes Prabhanjan_1 commented Dec 8, 2016 reply Follow Share yes.. 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share then how is answer B? 0 votes 0 votes Prabhanjan_1 commented Dec 8, 2016 reply Follow Share I think the option itself is wrong. 0 votes 0 votes Aghori commented Dec 8, 2016 reply Follow Share Let we need to remove x edges from n(n-1)/2. A graph is necessarily be disconnected if it has (n-1)(n-2)/2. n(n-1)/2 - x = (n-1)(n-2)/2 => x = n-1. Therefore answer is c. 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share yes, but vertices are in terms of 'm' 0 votes 0 votes Aghori commented Dec 8, 2016 reply Follow Share Yes. Low accuracy syndrome. 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share so D is correct ryt? 0 votes 0 votes Aghori commented Dec 8, 2016 reply Follow Share No just replace n by m. 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share how?.. n-1 and m-1 are two completely differnt things. ok leave it anyway 0 votes 0 votes Aghori commented Dec 8, 2016 reply Follow Share Yes. Sorry. Didn't see carefully. 0 votes 0 votes papesh commented Dec 8, 2016 reply Follow Share circuit rank =e-n+1 gives number of edges to make spanning tree ... if we remove one more edge graph will be disconnected...inplace of e-n they have done e-n+2... 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share n refers to edges @gabbar. in ur case n refers to vertices 0 votes 0 votes Kapil commented Dec 8, 2016 reply Follow Share Actually to make something connected, it should have more than $\frac{(n-1)(n-2)}{2}$ edges, i.e, just add one more edge. This gives $\frac{n^{2} - 3n + 4}{2}$ edges Now here in 2nd option, $C(m,2) -m + 2$ (n is replaced by m) This also gives $\frac{n^{2} - 3n + 4}{2}$ edges. Now, I am not getting the options :P 0 votes 0 votes Anusha Motamarri commented Dec 8, 2016 reply Follow Share we already know ME is famous for its mistakes ;) 2 votes 2 votes Please log in or register to add a comment.