2,237 views
Consider a simple undirected graph of $10$ vertices. If the graph is disconnected, then the maximum number of edges it can have is _______________ .

@Nisha Bharti @Abhrajyoti00 Neither cut vertices nor cut edges exist in a complete graph with $\geq 3$ vertices.

To find cut vertices or cut edges, you have to delete only “one” vertex or “one” edge at a time. The general definition says:

A cut-edge or cut-vertex of a graph is “an” edge or “a” vertex (respectively) whose deletion increases the number of components.

We write $G \ – \ e$ for deleting an edge $e$ and $G \ – \ v$ for deleting a vertex $v.$

Here, you are deleting a set of edges for a complete graph which is denoted by subgraph $G \ - \ M$ where M is the set of edges. When we delete a set of vertices then it is called “Induced Subgraph” which is denoted by $G \ – \ S$ where $S$ is set of vertices.

In case of undirected complete graph with $\geq 3$ vertices, deletion of any of the single edges would not increase the number of components, so here cut edge(s) does not exist but if you have $K_2$ then you will increase the number of component by deleting one edge which is the only edge, so in $K_2,$ there will be one cut edge.

For $K_3,K_4,..$ etc, you will not get any cut edges. You could also verify from wiki.

@ankitgupta.1729 Thank u sir now my doubt is clear.

@ankitgupta.1729 Sir, always to the rescue with true facts. Thank you :)

We need a disconnected graph, that too with the maximum number of edges possible. To satisfy both these conditions, we can say that we must have a graph with exactly two components, each of which is a complete graph.

To maximize the number of edges, we should make a complete graph with $9$ vertices, and isolate one vertex.

Hence, we get $36$ edges. (In a complete graph on n vertices, we have ${}^nC_2$ edges. So, for a complete graph on 9 vertices, we have ${}^9C_2 = 36$ Edges)

In general, we can say that, for n vertices disconnected graph, maximum number of edges possible is ${}^{(n-1)}C_2$.

Yes sir but before disconnection i think cut edges will be 9, right sir? because total no. of edges in 10 vertices are 45, if 1 vertex will be isolated from 10 vertices it means 9 edges will be remove that is cut edges, if i am not wrong.

@Nisha Bharti What you are saying is w.r.t just the above solution. This solution was assumed to have $2$ disconnected components, one having only $1$ vertex, and other having $9$ vertices. In that case also we will get $0$ min cut-edges. Because the 1st component is already disconnected.

@Abhrajyoti00 ok ok now got it.

To get maximum number of edges we can isolate 1 vertex and make a complete graph of 9 vertices.

Max. number of edges with 9 vertices = $\binom92$ = $\frac{9!}{7! *2} = 36$

by

Please refer the following image with two concepts:

https://gateoverflow.in/320460/Cmi2018-b-3

The first part is a direct exercise problem in Kenneth Rosen textbook. If we see the contrapositive statement, we find e is at most (n-1) C 2
by