GATE 2024 CS (CS1) – Question 51
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?
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).
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2024 CS (CS2) Q17
- GATE 2024 CS (CS2) Q51
- GATE 2024 CS (CS2) Q60
- GATE 2023 CS Q55
- GATE 2022 CS Q30
- GATE 2022 CS Q37
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →