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

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

---

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

---

Here is visual representation.

Answer 1

Detailed Video Solution Here: Maximum number of edges in disconnected graph

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

---

Some Important Questions on Connected & Disconnected Graphs: Important Questions on Connected, Disconnected Graphs (Click HERE)

Comments

@Saransh Maurya Read it again, no one has removed vertex it is there but that vertex is not connected(i.e., isolated vertex that also means disconnected which is given in question).  

---

ok i got it

---

@Saransh Maurya, I did Not remove any vertex or edge.

See Detailed Video Solution Here: https://youtu.be/G8AeYi5PMe8?t=51&feature=shared

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:

Comments

When we say a graph is disconnected do we mean removal of edge or vertex ?

---

from a connected graph of 10 vertices, it is removal of 1 vertex to make the graph disconnected not any egde.

There are two disconnected  components:

1 Single vertex

2. A complete graph of containing 9 vertices.

Answer 4

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

Answer 5

Since the graph needs to be disconnected with maximum number of edges. So 1 Vertex needs to be left. So I can connect remaining 9 Vertices with each other and form a complete graph.

Connecting 1st vertex with remaining 8 vertices=8 edges.

Connecting 2nd vertex with remaining 7 vertices (because it is already connected to 1st vertex)=7 edges.

Connecting 3rd vertex with 6 vertices (because it is already connected to 1st vertex and 2nd vertex)=6 edges.

This is an arithmetic progression with 8 terms, first term 8, and common difference −1.

It forms an A.P. = 8+7+6+...........+1

Sum of A.P.= n/2 [2a+(n-1)d]

                 = 8/2 [2*8 + 7(-1)]

                 = 4[16-7]

                 = 4 * 9

                  = 36

Hence, we get 36 edges.

Answer 6

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