GATE CSE
First time here? Checkout the FAQ!
x
+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 in Graph Theory by (239 points)   | 326 views

1 Answer

+2 votes
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.


Top Users Aug 2017
  1. Bikram

    4990 Points

  2. ABKUNDAN

    4730 Points

  3. akash.dinkar12

    3488 Points

  4. manu00x

    3286 Points

  5. rahul sharma 5

    3166 Points

  6. makhdoom ghaya

    2510 Points

  7. just_bhavana

    2398 Points

  8. stblue

    2144 Points

  9. Tesla!

    2066 Points

  10. joshi_nitish

    1796 Points


25,022 questions
32,160 answers
74,903 comments
30,202 users