Q41

MSQ2 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?

(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$

Loading…