GATE 2024 CS1 Q.51: solution and answer

Official answer: B, CSource: Official answer key, GATE 2024 CS1 (IISc Bengaluru)

1. Take a proper colouring of $G$ with exactly $k$ colours, where $k=\chi (G)$. Each colour class is an independent set, and the $k$ classes partition the $n$ vertices.

2. (A) Test with the odd cycle $C_5$: $\chi (C_5)=3$, but $C_5$ has no triangle, so it has no $K_3$. (A) is not always true.

3. (B) The $k$ classes cover $n$ vertices, so by the pigeonhole principle one class has at least $\lceil n/k\rceil \ge n/k$ vertices. That class is an independent set. (B) is always true.

4. (C) Suppose two colour classes had no edge between them. Merging them would give a proper colouring with $k-1$ colours, which contradicts $\chi (G)=k$.

5. So every pair of the $k$ classes has at least one edge between them. The pairs of classes number $\left(\genfrac{}{}{0ex}{}{k}{2}\right)=\frac{k(k-1)}{2}$, and the edges counted for different pairs are distinct. Hence $G$ has at least $\frac{k(k-1)}{2}$ edges. (C) is always true.

6. (D) Test with $K_k$: $\chi (K_k)=k$, but every vertex has degree $k-1<k$. (D) is not always true.

7. Hence the correct options are (B) and (C).