The GATE Grind

GATE 2018 CS – Question 28

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 1 mark · Numerical answer

The chromatic number of the following graph is ________.

Diagram for GATE 2018 CS question 28

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 3

Explanation

The graph contains a triangle (for example $a$, $b$, $c$), so at least 3 colours are needed, and a proper 3-colouring exists. So the chromatic number is 3.