Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
Correct Answer:
36
Solution:
A disconnected graph contains at least two components. To get the maximum number of edges, we can divide the graph into two components one with 9 vertices and the other with one vertex.
The maximum number of edges in the first component is 9(9-1)/2 = 36 and the maximum number of edges in the second component is 0.
The total number of edges a simple undirected disconnected graph of 10 vertices can have is 36 + 0 = 36.