The chromatic number of the following graph is …
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2018 · Q18
Time

Your answerNumerical answer
Solution
Official answer: 3 (±0)
Discrete MathematicsTo determine the chromatic number (the minimum number of colors needed to color the vertices such that no two adjacent vertices share the same color):
Lower Bound: The graph contains triangles (cliques of size 3), for example the subgraph induced by vertices . Hence, at least 3 colors are required:
3-Coloring Assignment: Let the three colors be :
Assign color $1$ to vertex $a$: $c(a) = 1$
Assign color $2$ to vertex $b$: $c(b) = 2$
Assign color $3$ to vertex $c$: $c(c) = 3$
Vertex is adjacent to and , so assign .
Vertex is adjacent to and , so assign .
Vertex is adjacent to , , and , so assign .
Verification: All adjacent vertex pairs have distinct colors:
Edges with color pairs: , , , , , , , , , .
Since a valid 3-coloring exists and the graph cannot be colored with 2 colors, the chromatic number is 3.
Try the question first, then check your work.
Examiner trap
Identify odd cycles or triangles to find the lower bound, and test if 3 colors are sufficient to properly color all vertices.
This Discrete Mathematics previous year question is Q18 of the GATE CSE 2018 paper. Find more GATE CSE PYQs on Discrete Mathematics in Engineering Mathematics, or browse all GATE CSE PYQs.
Free diagnostic
Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Discrete Mathematics PYQs now with no account.
An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.
Discrete Mathematics has 50 GATE CSE PYQs across 23 papers from 2011 to 2026. 10 of them are 1-mark NAT questions like this one, and it is the only one in GATE CSE 2018.
How GATE tests Discrete MathematicsIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.