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

GATE 2022 · Discrete Mathematics · Graph Connectivity · medium

Answer: 36

1. Choose optimal disconnected structure: Isolate vertex 10 (degree 0). Place remaining 9 vertices in K_9. Any edge from vertex 10 would connect the graph. Alternative splits give fewer edges: e.g., K_8 + K_2 gives C(8,2)+C(2,2) = 28+1 = 29 < 36.
2. Count edges in K_9: K_9 has C(9,2) = 9*8/2 = 36 edges. The isolated vertex contributes 0 edges. Total = 36.