GATE 2022 CS Q.30: solution and answer

Official answer: 36Source: Official answer key, GATE 2022 CS (IIT Kharagpur)

1. A disconnected graph has at least two components. To maximise edges, first take exactly two components, with $k$ and $10-k$ vertices, where $1\le k\le 9$. Merging extra components into one of these only allows more edges, so two components is enough.

2. A simple graph on $m$ vertices has at most $\left(\genfrac{}{}{0ex}{}{m}{2}\right)$ edges, reached by $K_m$. So the number of edges is at most $f(k)=\left(\genfrac{}{}{0ex}{}{k}{2}\right)+\left(\genfrac{}{}{0ex}{}{10-k}{2}\right)$.

3. Expand: $f(k)=\frac{k(k-1)+(10-k)(9-k)}{2}=k^2-10k+45$. This is a parabola opening upward with its minimum at $k=5$, so on $1\le k\le 9$ it is largest at the ends $k=1$ and $k=9$.

4. Check the values: $f(1)=1-10+45=36$, $f(2)=4-20+45=29$, $f(5)=25-50+45=20$. These agree with $0+\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$, $1+\left(\genfrac{}{}{0ex}{}{8}{2}\right)=29$ and $10+10=20$.

5. The maximum is $36$, reached by $K_9$ together with one isolated vertex (a graph with 10 vertices, disconnected).

6. General rule: a disconnected simple graph on $n$ vertices has at most $\left(\genfrac{}{}{0ex}{}{n-1}{2}\right)$ edges. Here $\left(\genfrac{}{}{0ex}{}{9}{2}\right)=36$.