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