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

For all graph problems the trick which works is scale down the problem.

It's really simple. Just take 5 vertices.

Now try to draw disconnected graphs. It's simple to understand that if we take more than 3 components we can't have max edges possible because the vertices will be spreaded into different components

The possibilities can be

Connected components of 3 vertices & connected components of 2 vertices.

-> with 3 vertices we can have max 3 edges that is a complete graph and with 2 vertices we can have 1 edge. Total 4 edges

Connected components of 4 vertices & connected components of 1 vertices.

-> with 4 vertices a complete graph has max 6 edges and with 1 vertices 0 edge possible. So total 6 edges.

So we got the max when we form 2 connected component with n-1 vertices and last vertex.

And then form a complete graph with n-1 vertices that's the answer.

For 10 vertices do the same now.

Complete graph of 9 vertices gives 36 edges

Last vertex gives 0 edge

So total 36 edges