GATE CS 2004 Q77 — Graphs: Connectivity, Matching, Colouring

The given graph is a wheel graph consisting of an outer $5$-cycle (pentagon) and a central hub vertex connected to all $5$ outer vertices.

1. An odd cycle, such as the outer $5$-cycle, requires at least $3$ colors to be properly colored because it is not bipartite.
2. The central vertex is adjacent to all $5$ vertices of this outer cycle, meaning it cannot share a color with any of them.
3. This forces the use of a $4^{\text{th}}$ distinct color for the central vertex.

Thus, the minimum number of colors required (the chromatic number) is $\chi(G) = 4$.