GATE Overflow | Data Structures | Test 1 | Question: 27

Question

Consider a complete graph of 10 vertices. The minimum no. of edge removals required to make the graph disconnected is ______

Comments

@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.

 

---

Isnt it obvious that we can chose the edges to remove?

---

@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?

---

@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)

Answer 1

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 .

Answer 2

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

Answer 3

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

Comments

@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.

---

No, you are seeing it wrong. Graph here is complete as per question. Now to disconnect it we need to isolate only 1 vertex.