Skip to content
GATEiit

GATE CSE 2024 Session 1 Q51: Consequences of a graph having chromatic number k

Question

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?

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: B, C (official GATE 2024 final answer key)

Concept used: Colour classes are independent sets, and an optimal colouring has an edge between every two classes.

First step: Pigeonhole: some colour class has at least n/kn/k vertices. For (A) and (D), test C5C_5 and KkK_k.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2024 Session 1 CS question paper and final answer key, organised by IISc Bangalore. Question paper · Answer key

More Engineering Mathematics PYQs

PracticePractise Engineering Mathematics questions →Full paperAll GATE CSE 2024 Session 1 questions →