Question

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 \( n/k \)
• C. \( G \) contains at least \( k(k-1)/2 \) edges
• D. \( G \) contains a vertex of degree at least \( k \)

Answer 1

The Correct Option is B

Step 1: Independent set size.
An independent set is a set of vertices such that no two vertices are adjacent. For a graph with chromatic number \( k \), the graph can be partitioned into \( k \) independent sets. The largest independent set must have at least \( n/k \) vertices. Hence, (2) is true. Step 2: Number of edges.
The chromatic number \( k \) implies there is at least a complete subgraph \( K_k \). A complete subgraph with \( k \) vertices has \( k(k-1)/2 \) edges. Therefore, \( G \) must contain at least \( k(k-1)/2 \) edges. Hence, (3) is true. Step 3: Remaining options.
Option (1) is not necessarily true because the graph may not contain a complete subgraph with \( k \) vertices.
Option (4) is also not necessarily true because there may not be a vertex of degree \( k \). Final Answer: \[ \boxed{(2), (3)} \]