GATE CS 2018 Q18 — Graphs: Connectivity, Matching, Colouring

To find the chromatic number of the given graph, we determine the minimum number of colors needed to color its vertices such that no two adjacent vertices share the same color.

1. Lower Bound: The graph contains an odd cycle of length 5. Since any odd cycle requires at least 3 colors to be properly colored, the chromatic number $\chi(G) \ge 3$.
2. Upper Bound (3-Coloring): We can show that the graph is 3-colorable by assigning colors from $\{1, 2, 3\}$ to the vertices:
   • Color the outer 5-cycle vertices sequentially as: $1, 2, 3, 1, 2$.
   • For the remaining two inner vertices, we can assign them colors from $\{1, 2, 3\}$ that do not conflict with their neighbors.

Since a valid 3-coloring exists and fewer than 3 colors are impossible due to the odd cycle, the chromatic number of the graph is 3.