GATE CS 2024 Set 2 Q50 — Graphs: Connectivity, Matching, Colouring

To find the chromatic number of the given graph, we can analyze its cycle structure and attempt to color it using the minimum number of colors.

1. Check for 1-colorability: A graph has a chromatic number of $1$ if and only if it has no edges (an empty graph). Since this graph contains edges, its chromatic number must be at least $2$.
2. Check for 2-colorability (Bipartiteness): A graph is $2$-colorable if and only if it is bipartite, which is equivalent to saying that the graph contains no cycles of odd length (such as triangles $C_3$, pentagons $C_5$, etc.).
3. Analyzing the given graph:
   • By inspecting the graph, we observe that all cycles are of even length (e.g., $4$-cycles, $8$-cycles). There are no odd cycles present.
   • We can successfully perform a $2$-coloring of the vertices. If we start by coloring any vertex with Color 1, all of its neighbors must be colored with Color 2, their neighbors with Color 1, and so on. This process completes without any conflicts.

Since the graph is bipartite and contains at least one edge, its chromatic number is exactly 2.