The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let $G$ be any graph with $n$ vertices and chromatic number $k$. Which of the following statements is/are always TRUE?

Let $G = (V, E)$ be a graph with $|V| = n$ and chromatic number $\chi(G) = k$.

• Option (A) is FALSE: A graph with chromatic number $k$ does not necessarily contain a clique (complete subgraph) $K_k$. For example, the 5-cycle $C_5$ has chromatic number $k = 3$, but its maximum clique size is $2$ (it contains no $K_3$). More generally, Mycielski's construction generates triangle-free graphs with arbitrarily high chromatic numbers.

• Option (B) is TRUE: A proper $k$-colouring partitions $V$ into $k$ independent sets (colour classes) $V_1, V_2, \dots, V_k$. By the Pigeonhole Principle, at least one of these independent sets must have size at least:

  $$\left\lceil \frac{n}{k} \right\rceil \ge \frac{n}{k}$$

• Option (C) is TRUE: In an optimal $k$-colouring, there must be at least one edge between every pair of distinct colour classes. If there were no edge between some pair of colour classes $V_i$ and $V_j$, we could merge $V_i$ and $V_j$ into a single colour class, resulting in a valid proper colouring using $k-1$ colours, which contradicts the minimality of $k$. Since there are $\binom{k}{2} = \frac{k(k-1)}{2}$ pairs of colour classes, $G$ must have at least $\frac{k(k-1)}{2}$ edges.

• Option (D) is FALSE: For the 5-cycle $C_5$, $k = 3$, but every vertex has degree $2$, which is strictly less than $k = 3$. Hence, $G$ does not necessarily have a vertex of degree at least $k$ (though the maximum degree $\Delta(G) \ge k - 1$ by Brooks' theorem / greedy bound).

Therefore, the correct options are B and C.