GATE 2024 CS (CS2) – Question 60

Engineering Mathematics · Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) · 2 marks · Numerical answer

The chromatic number of a graph is the minimum number of colours used in a proper colouring of the graph. The chromatic number of the following graph (an 8-vertex graph drawn as an octagon with additional chords) is _________

Diagram for GATE 2024 CS (CS2) question 60

Practise this question in The GATE Grind →

Show answer and explanation

Correct answer: 4

Explanation

The graph contains a K4 subgraph among its chorded vertices, forcing at least 4 colours, and a valid 4-colouring exists. Chromatic number = 4.