GATE CS 2024 Set 1 | Question 51

MSQ · 2 marks

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?

  1. Option A: \(G\) contains a complete subgraph with \(k\) vertices
  2. Option B: \(G\) contains an independent set of size at least \(n/k\) (correct)
  3. Option C: \(G\) contains at least \(k(k - 1)/2\) edges (correct)
  4. Option D: \(G\) contains a vertex of degree at least \(k\)

Answer

(B), (C)

Explanation

Take a proper colouring with exactly \(k\) colours. Its colour classes are independent sets that split the \(n\) vertices into \(k\) groups.

  • (B) True: the largest of the \(k\) classes has at least \(n/k\) vertices.
  • (C) True: every two colour classes must be joined by at least one edge, otherwise they could share a colour and \(k - 1\) colours would do. That gives at least \(\binom{k}{2} = k(k - 1)/2\) edges.
  • (A) False: the 5-cycle needs 3 colours but contains no triangle.
  • (D) False: the complete graph \(K_{k}\) has chromatic number \(k\), yet every vertex has degree \(k - 1\).

Answer: B, C