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

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

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →