Computer Science And Engineering

Computer Science And EngineeringEngineering MathematicsMultiple Select (MSQ)2 Marks
Q14.

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. Let GG be any graph with nn vertices and chromatic number kk. Which of the following statements is/are always TRUE?

A
GG contains a complete subgraph with kk vertices
B
GG contains an independent set of size at least n/kn/k
C
GG contains at least k(k1)/2k(k - 1)/2 edges
D
GG contains a vertex of degree at least kk