GATE CS 2024 Set 1 Q41 — Graphs: Connectivity, Matching, Colouring

Let $G$ be a graph with $n$ vertices and chromatic number $\chi(G) = k$. This means $G$ can be properly colored using $k$ colors, but not with $k-1$ colors.

Let us analyze each option:

• Option A: $G$ contains a complete subgraph with $k$ vertices (False)
  A graph can have a high chromatic number without containing a large clique. For example, the 5-cycle $C_5$ has chromatic number $k = 3$, but its largest complete subgraph is $K_2$ (an edge). More generally, by Mycielski's construction, there exist triangle-free graphs with arbitrarily large chromatic numbers.


• Option B: $G$ contains an independent set of size at least $n/k$ (True)
  A proper $k$-coloring partitions the $n$ vertices of $G$ into $k$ independent sets (color classes). By the Pigeonhole Principle, if $n$ vertices are partitioned into $k$ sets, at least one of these sets must contain at least: $$\left\lceil \frac{n}{k} \right\rceil \ge \frac{n}{k} \text{ vertices.}$$ Since each color class is an independent set, $G$ must contain an independent set of size at least $n/k$.


• Option C: $G$ contains at least $k(k-1)/2$ edges (True)
  Let $V_1, V_2, \dots, V_k$ be the $k$ color classes in a proper $k$-coloring of $G$. For any two distinct color classes $V_i$ and $V_j$ ($1 \le i < j \le k$), there must be at least one edge between them. If there were no edges between some $V_i$ and $V_j$, we could merge these two classes into a single color class, resulting in a proper coloring with $k-1$ colors, which contradicts that the chromatic number is $k$. Since there are $\binom{k}{2} = \frac{k(k-1)}{2}$ pairs of color classes, and each pair has at least one edge connecting them, $G$ must contain at least $\frac{k(k-1)}{2}$ edges.


• Option D: $G$ contains a vertex of degree at least $k$ (False)
  Consider the complete graph $K_k$. Its chromatic number is $k$, and every vertex has degree exactly $k-1$. There is no vertex of degree $\ge k$.