GATE CSE
First time here? Checkout the FAQ!
x
+2 votes
376 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 (335 points) 1 9 17 | 376 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 (16.4k points) 15 135 253
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.


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
Top Users Oct 2017
  1. Arjun

    23678 Points

  2. Bikram

    17278 Points

  3. Habibkhan

    8960 Points

  4. srestha

    6450 Points

  5. Debashish Deka

    5478 Points

  6. jothee

    5128 Points

  7. Sachin Mittal 1

    4882 Points

  8. joshi_nitish

    4486 Points

  9. sushmita

    4032 Points

  10. Rishi yadav

    3974 Points


Recent Badges

Notable Question Sedhu Raman
Notable Question cse23
Notable Question vishwa ratna
Notable Question learner_geek
Popular Question Devshree Dubey
Popular Question nish kim
Popular Question Simar sandhu
Popular Question Rashi Gupta
Notable Question Akriti sood
Popular Question Samujjal Das
27,407 questions
35,256 answers
84,506 comments
33,480 users