GATE 2024 CS (CS2) – Question 60
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 _________

Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: 2 to 2
Explanation
Label the eight outer vertices clockwise starting at the upper-left vertex as $v_0,v_1,\ldots,v_7$. Every drawn edge joins an even-indexed vertex to an odd-indexed vertex. Crossings without black dots are not extra vertices.
Colour $\{v_0,v_2,v_4,v_6\}$ with one colour and $\{v_1,v_3,v_5,v_7\}$ with another. This is a proper 2-colouring. At least two colours are necessary because the graph has edges.
The chromatic number is **2**, matching the final key. The earlier claim of a K4 subgraph was false.
More Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions
- GATE 2023 CS Q55
- GATE 2022 CS Q30
- GATE 2022 CS Q37
- GATE 2022 CS Q50
- GATE 2022 CS Q52
- GATE 2022 CS Q58
All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →