GateAI
Graph Theory

GATE CSE 2024 Set 2 · Q60

NAT2 marksEasy

Time

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 ________

GATE CSE 2024 Set 2 Q60 diagram

Your answerNumerical answer

Enter a value to check

Solution

Step-by-step verified solution

Official answer: 2

Graph Theory

A graph has a chromatic number of 22 if and only if it is bipartite and contains at least one edge (i.e., it contains no odd-length cycles).

  1. Let us partition the 88 vertices into two disjoint sets V1V_1 and V2V_2 of 44 vertices each.

  2. By observing the graph structure, no two vertices in V1V_1 share an edge, and no two vertices in V2V_2 share an edge. All edges in the graph only run between vertices in V1V_1 and vertices in V2V_2.

  3. Since the graph is bipartite and contains edges, it can be properly colored using only 22 colors (assigning color 1 to all vertices in V1V_1 and color 2 to all vertices in V2V_2).

  4. Since the graph contains edges, it cannot be colored with 1 color.

Thus, the chromatic number χ(G)=2\chi(G) = 2.

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

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

Where do you stand for GATE?

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.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Graph Theory in GATE CSE

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 Theory

More from GATE CSE 2024 Set 2

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2024 Set 2 · Q60 · NAT

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

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.