GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
202 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 (219 points)   | 202 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 (14.7k 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 Jun 2017
  1. Bikram

    3912 Points

  2. Arnab Bhadra

    1526 Points

  3. Hemant Parihar

    1502 Points

  4. Niraj Singh 2

    1501 Points

  5. Debashish Deka

    1480 Points

  6. junaid ahmad

    1432 Points

  7. pawan kumarln

    1286 Points

  8. Rupendra Choudhary

    1242 Points

  9. rahul sharma 5

    1240 Points

  10. Arjun

    1232 Points

Monthly Topper: Rs. 500 gift card
Top Users 2017 Jun 26 - Jul 02
  1. pawan kumarln

    418 Points

  2. akankshadewangan24

    334 Points

  3. Arjun

    272 Points

  4. Debashish Deka

    234 Points

  5. Abhisek Das

    230 Points


23,433 questions
30,149 answers
67,606 comments
28,486 users