The GATE Grind

GATE 2024 CS (CS1) – Question 51

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Multiple select

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. $G$ contains a complete subgraph with $k$ vertices
  2. $G$ contains an independent set of size at least $n/k$
  3. $G$ contains at least $k(k-1)/2$ edges
  4. $G$ contains a vertex of degree at least $k$

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: (B) $G$ contains an independent set of size at least $n/k$; (C) $G$ contains at least $k(k-1)/2$ edges

Explanation

Largest colour class has ≥ n/k vertices and is independent (B). Every pair of colour classes must have an edge, else classes could merge, so ≥ k(k−1)/2 edges (C). A fails (odd cycles with k=3), and D fails in general (a vertex of degree ≥ k−1 is guaranteed, not k).