Consider a simple undirected graph of 10 vertices. If the graph is…
2022
Consider a simple undirected graph of 10 vertices. If the graph is disconnected, then the maximum number of edges it can have is ____________.
Attempted by 163 students.
Show answer & explanation
Correct answer: 36
Key idea: to maximize edges while keeping the graph disconnected, make one component as small as possible and make the other component complete.
With 10 vertices, the smallest disconnected component has size 1 (an isolated vertex).
The remaining 9 vertices can form a complete graph, which maximizes edges among them.
Number of edges in a complete graph on 9 vertices is C(9,2) = 9×8/2 = 36.
Therefore the maximum number of edges in a disconnected simple undirected graph with 10 vertices is 36.