GATE CSE 2022 | Question: 20

Question

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

Comments

@Abhrajyoti00 What is the minimum no. of edged (cut-edges)  to disconnect this graph?

---

@Nisha Bharti Don’t you think the answer to minimum no. of edged (cut-edges) to disconnect this graph must be $0$? Because it’s given that it is a disconnected graph. Why not assume all $10$ vertices to be disconnected as $10$ individual components. So no cut edges :) 

---

@Abhrajyoti00 Yes it is also possible, so no cut edges :(

---

@Abhrajyoti00 btw i want to ask that, what is the minimum no. of cut edges with minimum no. of cut vertex in the complete graph with 10 vertices?

---

@Nisha Bharti Min no of cut edges for a complete graph with $n$ vertices is $n-1$. This is because min no of edges in an undirected connected graph is $n-1$. Hence if we remove those $n-1$ edges, the graph will be disconnected.

(I am not sure of this. @ankitgupta.1729 Sir, can you please confirm)?

Min no. of cut vertices in a complete graph with $n$ vertices is $n$ itself. This is because there are no cut vertices in a $Kn$. Any vertex we cut, we will find other vertices to be still connected. A complete graph has no vertex cut - Mathematics Stack Exchange

---

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

Answer 1

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

Comments

@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 1^st component is already disconnected. 

It’s not asking “after disconnection”. It has already been mentioned about “disconnected graph”

---

@Abhrajyoti00 ok ok now got it.

---

The question is basically asking the maximum number of edges in a $K_9$ graph.

Answer 2

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$

Answer: 36 edges

Answer 3

Please refer the following image with two concepts:

Answer 4

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