GATE CS 2024 Set 2 — Question 60

The chromatic number of a graph is the smallest number of colors needed to color the vertices so that no two adjacent vertices share the same color.Let's analyze the structure of the given graph:

• The outer vertices form a cycle of length 4 ($C_4$).
• The inner vertices form a cycle of length 4 ($C_4$).
• Each outer vertex is connected to two inner vertices.

3. Bipartite Check: A graph is bipartite (chromatic number 2) if it contains no odd cycles. Let's attempt to 2-color the graph with colors Red (R) and Blue (B).

• Color the outer cycle alternatingly: Top-Outer (R), Right-Outer (B), Bottom-Outer (R), Left-Outer (B). This is valid for the outer square.
• Color the inner cycle alternatingly: Top-Inner (R), Right-Inner (B), Bottom-Inner (R), Left-Inner (B). This is valid for the inner square.
• Now check the cross connections. Visually, the Top-Outer vertex (R) is connected to the Left-Inner (B) and Right-Inner (B) vertices. This is a valid connection (Red to Blue).
• Similarly, the Right-Outer vertex (B) connects to Top-Inner (R) and Bottom-Inner (R). This is valid (Blue to Red).
• By symmetry, all other connections also respect the coloring (Red connected only to Blue).

Since we can color all vertices with 2 colors such that no adjacent vertices have the same color, the graph is bipartite. The chromatic number of a bipartite graph with at least one edge is 2.Therefore, the chromatic number is 2.