GATE CS 2022 Q.30: Graph Theory

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

Your answer

Official answer and solution

Official answer: 36
From: Official GATE 2022 answer key

Solution

Maximize the sum of edges across components by partitioning the 10 vertices into one isolated vertex and one complete graph.

A disconnected graph on $n$ vertices must have at least 2 connected components.

Let the components have sizes $n_1$ and $n_2$ such that $n_1 + n_2 = n$ with $n_1, n_2 \ge 1$ . The maximum number of edges in a graph with these components occurs when each component is a complete graph ( $K_{n_1}$ and $K_{n_2}$ ):

|E| = \binom{n_1}{2} + \binom{n_2}{2}

For $n = 10$ , this sum is maximized when the component sizes are as unequal as possible, namely $n_1 = 1$ and $n_2 = 9$ :

|E|_{\max} = \binom{1}{2} + \binom{9}{2} = 0 + \frac{9 \times 8}{2} = 36

Thus, the maximum number of edges in a disconnected simple graph on 10 vertices is 36.

Final answer

Common trap

Partitioning the vertices into two equal components of 5 vertices, which gives only $\binom{5}{2} + \binom{5}{2} = 10 + 10 = 20$ edges.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2022 Computer Science and Information Technology (CS)
Question: 30 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source