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? A. G contains a complete subgraph with k vertices. B. G contains an independent set of size at least ceil(n/k). C. G contains at least k*(k-1)/2 edges. D. G contains a vertex of degree at least k.

GATE 2024 · Discrete Mathematics · Graph Coloring · medium

Answer: B, C

1. Prove B: independent set of size >= ceil(n/k): The k colour classes partition n vertices. By pigeonhole, the largest class has at least ceil(n/k) vertices. Each class is an independent set. So G always contains an independent set of size >= ceil(n/k).
2. Prove C: at least k*(k-1)/2 edges: There are C(k,2) = k(k-1)/2 pairs of distinct colour classes. If any pair of classes had no edge between them, those two classes could be merged into one, contradicting that k is the minimum. So each pair of classes contributes at least 1 edge, giving at least k(k-1)/2 edges in total.
3. Disprove A and D: A: FALSE. Mycielski graphs are triangle-free (no K_3) yet have arbitrarily large chromatic number. So chi = k does not imply K_k is a subgraph. D: FALSE. We know Delta(G) >= chi(G) - 1 (from chi <= Delta+1), but not necessarily >= chi(G) = k. For example, chi(C_5) = 3 but Delta(C_5) = 2 = k-1 < k.