0 votes 0 votes Consider a complete graph of 10 vertices. The minimum no. of edge removals required to make the graph disconnected is ______ DS go-ds-1 data-structures graph-theory numerical-answers + – Arjun asked Oct 10, 2016 Arjun 620 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply chauhansunil20th commented Jan 10, 2019 reply Follow Share @Arjun I think answer should be 37. it shouldn't ne order dependent, removal of 9 edges won't give a disconnected graph always. anyway, minimum in worst case is 37, and for maximum answer will be 45. 0 votes 0 votes Arjun commented Jan 10, 2019 reply Follow Share Isnt it obvious that we can chose the edges to remove? 0 votes 0 votes chauhansunil20th commented Jan 10, 2019 reply Follow Share @Arjun shouldn't we consider the worst case as we always do? I will give you another example, "how many minimum edges are required so that a graph with 10 vertices doesn't remain disconnected?" What will be your answer, 9? I don't think so, the answer will be, first we should connect 9 vertices completely and then add 1 more edge, so that graph is connected. so answer will be $(9*8)/2$ +1, and the answer for maximum will be $10*9/2 =45$ edges, right? 0 votes 0 votes prashant jha 1 commented Jan 24, 2019 reply Follow Share @chauhansunil20th Here we've been asked to find the "minimum" number of edges that is required to be removed so that we can get at least 2 connected components(so that we can say that graph is disconnected). Now a $K_{10}$ graph will have all it's vertices have degree 9. Let's choose any vertex out of the 10 possibilities. Now this vertex is connected to 9 other vertices . Only if i remove all the 9 edges , then I can guarantee that I will get two connected components right . A $K_{9}$ graph and one vertex. Otherwise , if less than 9 edges are removed , then there will be at least one edge that will keep the structure binded. Thus , with removal of 9 edges associated to a particular vertex , we can guarantee that we'll get a disconnected graph. This is also known as Edge connectivity. Edge connectivity <=(Min degree of a graph) 0 votes 0 votes Please log in or register to add a comment.
Best answer 7 votes 7 votes Out of 10 vertices, a graph is disconnected if 1 vertex is not reachable. So, remove that vertex and all the 9 edges pointed by other vertices to this vertex, hence making the graph disconnected . Kapil answered Oct 13, 2016 selected Jan 17, 2017 by Kapil Kapil comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes for complete graph there is edge between every pair of vertex , for graph of n nodes total edges are nC2 and each vertex has (n-1) degree by removing n-1 edges we can make it disconnected from one vertex and increase number of connected components I_am_winner answered Jul 16, 2018 I_am_winner comment Share Follow See all 2 Comments See all 2 2 Comments reply Deep Learner commented Jul 27, 2018 reply Follow Share @arjun sir. Sir I think max no. Edges for a graph of 10 vertices to get disconnected is 8. So ans should be 10c2 -8=37 The ans given is 9 that is for a particular case when we make a particular vertices isolated.It is not a general answer. For example if we delete one edge from any of 9 vertices total edge deleted is 9 but graph is still connected. But if I say I delete 37 edge from the graph it means no matter which edge I delete graph will get disconnected. 0 votes 0 votes Arjun commented Jul 27, 2018 reply Follow Share No, you are seeing it wrong. Graph here is complete as per question. Now to disconnect it we need to isolate only 1 vertex. 1 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes To disconnect a graph, all we need to do is isolate a single vertex. Each vertex is connected to rest of the vertices in a complete graph. So, here, each vertex is connected to 9 other vertices. Pick any random vertex, and remove all those 9 edges that connect the vertex to other vertices. => 9 JashanArora answered Dec 14, 2019 JashanArora comment Share Follow See all 0 reply Please log in or register to add a comment.