The Gateway to Computer Science Excellence
0 votes
186 views



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?

in Graph Theory by Boss (12k points)
recategorized by | 186 views
0
given in the question always ;
So what if n=4 and m=4 connected graph.??
0
yeah given "always" so even if there is one example which contradicts the given answer,that is not gonna be correct
0
yes..
0
then how is answer B?
0
I think the option itself is wrong.
0
  • 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
yes, but vertices are in terms of 'm'
0
Yes. Low accuracy syndrome.
0
so D is correct ryt?
0
No just replace n by m.
0
how?.. n-1 and m-1 are two completely differnt things. ok leave it anyway
0
Yes. Sorry. Didn't see carefully.
0
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
n refers to edges @gabbar. in ur case n refers to vertices
0
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
+2
we already know ME is famous for its mistakes ;)

Please log in or register to answer this question.

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,292 answers
198,234 comments
104,917 users