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

@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

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

---

@Nisha Bharti, the given graph is already disconnected.

---

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