GATE 2022 CS – Question 30
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 36
Explanation
To get the largest number of edges without connecting the graph, make it consist of exactly **two** components and make each component complete.
For two components of sizes $a$ and $b$ with $a+b=10$, the number of edges is $\binom a2+\binom b2$. This is largest when the sizes are as unequal as possible: $a=9,\ b=1$ (an isolated vertex).
$$\binom92+\binom12=36+0=\mathbf{36}.$$
For comparison, $a=b=5$ gives $10+10=20$ and $a=8,b=2$ gives $28+1=29$.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2022 CS Q37
- GATE 2022 CS Q50
- GATE 2022 CS Q52
- GATE 2022 CS Q58
- GATE 2021 CS (CS1) Q26
- GATE 2020 CS Q62
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →