GATE CSE 2022 Q30: Maximum edges in a disconnected simple graph on 10 vertices

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

Try it: numerical answer: type the value

Your answer

Numerical answer. No negative marking.

Show answer and explanation

Answer: 36 (official GATE 2022 final answer key)

Concept used: A disconnected graph with the most edges is a complete graph on $n-1$ vertices plus one isolated vertex.

First step: Count the edges of $K_9$ : $\binom{9}{2}$ .

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

Source: official GATE 2022 CS question paper and final answer key, organised by IIT Kharagpur. Question paper · Answer key