Question 51

Consider an optimal proper $k$-colouring of $G$, which partitions the $n$ vertices into $k$ colour classes $V_1, V_2, \dots, V_k$.

• (A) is FALSE: A graph with chromatic number $k$ need not contain $K_k$ as a subgraph (for example, the odd cycle $C_5$ has chromatic number $k = 3$ but contains no $K_3$).
• (B) is TRUE: Each colour class $V_i$ is an independent set, and $\sum_{i=1}^k |V_i| = n$. By the Pigeonhole Principle, $\max_i |V_i| \ge n/k$, so $G$ contains an independent set of size at least $n/k$.
• (C) is TRUE: Between every pair of distinct colour classes $(V_i, V_j)$ with $1 \le i < j \le k$, there must be at least one edge in $G$ (otherwise $V_i$ and $V_j$ could be merged into a single colour class, giving a valid $(k-1)$-colouring of $G$). Since there are $\binom{k}{2} = \frac{k(k-1)}{2}$ pairs of colour classes, $G$ must contain at least $k(k-1)/2$ edges.
• (D) is FALSE: A graph with chromatic number $k$ only requires maximum degree $\Delta(G) \ge k - 1$ (for example, $K_k$ has chromatic number $k$, and every vertex has degree $k - 1 < k$).