GATE CS 2024 Set 1 — Question 51

Let $\chi(G) = k$ be the chromatic number of the graph $G$ with $n$ vertices.(A) False. It is not necessary for a graph with chromatic number $k$ to contain a clique of size $k$ (a complete subgraph with $k$ vertices). For example, Mycielskian graphs can have an arbitrarily high chromatic number but remain triangle-free (clique number $\omega(G) = 2$). Another simple example is an odd cycle $C_5$ ($n=5$), which has $\chi(C_5) = 3$ but the largest clique is size 2.(B) True. In any proper $k$-colouring, the vertices $V$ are partitioned into $k$ colour classes $V_1, V_2, \dots, V_k$, where each $V_i$ is an independent set. Since $\sum_{i=1}^k |V_i| = n$, by the Pigeonhole Principle, at least one set $V_i$ must have size at least the average size, i.e., $|V_i| \ge \frac{n}{k}$. Thus, the independence number $\alpha(G) \ge \frac{n}{k}$.(C) True. In a minimal proper $k$-colouring with colour classes $V_1, \dots, V_k$, there must be at least one edge between every pair of colour classes $V_i$ and $V_j$ ($i \neq j$). If there were no edges between some $V_i$ and $V_j$, we could merge them into a single independent set (colour class), thereby colouring the graph with $k-1$ colours, which contradicts $\chi(G)=k$. Since there are $\binom{k}{2} = \frac{k(k-1)}{2}$ pairs of colour classes, and edges connecting distinct pairs are distinct, the graph must have at least $\frac{k(k-1)}{2}$ edges.(D) False. Consider the complete graph $K_k$. It has $n=k$ vertices and chromatic number $\chi(K_k) = k$. The degree of every vertex in $K_k$ is $k-1$. Thus, no vertex has a degree of at least $k$.