+1 vote
326 views
Assumed  undirected  graph  G  is  connected.  G  has  6­vertices  and  10  edges.  Find
the minimum number of edges whose deletion from graph G is always  guarantee
that it will become disconnected.
asked | 326 views

i. G is connected graph
ii. G has 6 vertices
iii. G has 10 edges

in ideal case G needs 5(n-1) edges to be connected. hence if we remove 6 edges
then G will be left with 4 edges and be disconnected guranteed
answered by Veteran (15.1k points)
vijay,i dun think 6 is the correct answer as it is askign for minimum,,i think if we remove only 3 edges then also it will be disconnected...

if we have to make a graph as disconnected,take a node with the minimum degree and remove all its incoming edges..

for a graph with 6 vertices and 10 edges,minimum degrees can be 2 or 3.so,if we remove 3 edges,then graph will be disconnected

G is always  guarantee that it will become disconnected.

take any graph with 6 vertices and 10 edges,you will find either 2 or 3.and moreover,with 6 vertices,it wont have any vertex with degree more than 5..so,6 is definitly not the minimum option.

you can give any counter example
i think you're right
yes,but i found one more thing..though 3 are enough to disconnect it but if we randomly remove those 3 edges from the graph..then we might not get disconnected graph in all the cases.those three edges have to be edges from the node having degree 3.but if we remove 'any' 6 then definitly we will get disconnected.but thats not the minimum..

i am confused here,
then 6 is the correct answer
@Vijay. Maximum degree is 5.

So, in order to guarantee to make it disconected, 5 edges removal is neceaasary.

+1 vote