GATE CS 2022 Q20 — Graphs: Connectivity, Matching, Colouring

To find the maximum number of edges in a disconnected simple undirected graph with $n = 10$ vertices, we need to partition the vertices into at least two disconnected components such that the sum of the edges in these components is maximized.

Let the graph be partitioned into two components with $n_1$ and $n_2$ vertices, where $n_1 + n_2 = 10$ and $n_1, n_2 \ge 1$. To maximize the edges, each component itself must be a complete graph (clique).

The total number of edges $E$ is given by:

To maximize this quadratic sum, the sizes of the components should be as unbalanced as possible. Thus, we choose:

• $n_1 = 9$ (a complete graph $K_9$)
• $n_2 = 1$ (an isolated vertex)

Calculating the maximum number of edges:

Any other partition (for example, $n_1 = 8$ and $n_2 = 2$) yields fewer edges:

Therefore, the maximum number of edges the disconnected graph can have is 36.