The GATE Grind

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: 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

All Discrete Mathematics: Graphs (Connectivity, Matching, Colouring) questions →