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

Dark Mode

0 votes

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

@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

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

0

@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

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

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

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

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

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**