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 …
Topic-wise GATE CS PYQs with verified steps
GATE CSE 2024 Set 2 · Q60
Time

Your answerNumerical answer
Solution
Official answer: 2
Graph TheoryA graph has a chromatic number of if and only if it is bipartite and contains at least one edge (i.e., it contains no odd-length cycles).
Let us partition the vertices into two disjoint sets and of vertices each.
By observing the graph structure, no two vertices in share an edge, and no two vertices in share an edge. All edges in the graph only run between vertices in and vertices in .
Since the graph is bipartite and contains edges, it can be properly colored using only colors (assigning color 1 to all vertices in and color 2 to all vertices in ).
Since the graph contains edges, it cannot be colored with 1 color.
Thus, the chromatic number .
Try the question first, then check your work.
Examiner trap
Check if the graph is bipartite (i.e., whether it contains any odd cycles). A non-empty bipartite graph can always be properly colored with 2 colors.
This Graph Theory previous year question is Q60 of the GATE CSE 2024 Set 2 paper. Find more GATE CSE PYQs on Graph Theory 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 Graph Theory 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.
Graph Theory has 21 GATE CSE PYQs across 14 papers from 2012 to 2026. 7 of them are 2-mark NAT questions like this one, and it is the only one in GATE CSE 2024 Set 2.
How GATE tests Graph TheoryIndependent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.