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

3 Answers

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 .
selected by
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
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

Answer:

Related questions

1 votes
1 votes
2 answers
1
Arjun asked Oct 10, 2016
460 views
What is the chromatic number of the following graph?
3 votes
3 votes
1 answer
2
Arjun asked Oct 10, 2016
503 views
The maximum number of possible edges in an undirected simple graph with $100$ vertices and $5$ components is ___
0 votes
0 votes
2 answers
3
Arjun asked Oct 10, 2016
559 views
A vertex having no incident edge is called -pendent vertex end vertexisolated vertex none of these