GATE CS 2002 Q1.4 — Graphs: Connectivity, Matching, Colouring

The problem asks for the chromatic number (the minimum number of colors required for vertex coloring) of a cycle graph $C_n$ with $n$ vertices ($n \ge 3$).

For any cycle graph $C_n$:

• If $n$ is even, we can alternate between $2$ colors. Thus, the chromatic number is $\chi(C_n) = 2$.
• If $n$ is odd, alternating $2$ colors will result in the first and last adjacent vertices having the same color. Thus, we need a third color, making the chromatic number $\chi(C_n) = 3$.

Let us evaluate the expression in Option D: $n - 2 \left\lfloor \frac{n}{2} \right\rfloor + 2$

• Case 1: $n$ is even
  Let $n = 2k$ for some integer $k$.
  $$n - 2 \left\lfloor \frac{n}{2} \right\rfloor + 2 = 2k - 2 \left\lfloor \frac{2k}{2} \right\rfloor + 2 = 2k - 2k + 2 = 2$$This matches the required $2$ colors.


• Case 2: $n$ is odd
  Let $n = 2k + 1$ for some integer $k$.
  $$n - 2 \left\lfloor \frac{n}{2} \right\rfloor + 2 = (2k+1) - 2 \left\lfloor \frac{2k+1}{2} \right\rfloor + 2 = 2k + 1 - 2k + 2 = 3$$This matches the required $3$ colors.

Since Option D correctly yields $2$ for even $n$ and $3$ for odd $n$, it is the correct representation.