Skip to content
GATEiit

GATE CSE 2024 Session 2 Q60: Chromatic number of an eight-vertex graph

Question

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 is _________

Eight vertices placed on an octagon with the outer octagon edges plus vertical, horizontal and diagonal chords; every vertex has degree 4
Tap the figure to enlarge

Try it: numerical answer: type the value

Numerical answer. No negative marking.
Show answer and explanation

Answer: 2 (official GATE 2024 final answer key)

Concept used: A graph is 2-colourable exactly when it is bipartite (has no odd cycle).

First step: Colour one vertex red, its four neighbours blue, and check whether the remaining vertices can all be red without conflict.

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 2 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 2 questions →