The GATE Grind

GATE 2022 CS – Question 30

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Numerical answer

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

The maximum is a complete graph on 9 vertices plus one isolated vertex, giving $\binom{9}{2}=36$ edges.