GATE CS 2009 Q2 — Graphs: Connectivity, Matching, Colouring

A fundamental theorem in graph theory states that a graph is bipartite if and only if it contains no odd cycles.

By definition, the vertices of a bipartite graph can be partitioned into two disjoint sets, say $V_1$ and $V_2$, such that every edge connects a vertex in $V_1$ to a vertex in $V_2$. Therefore, we can color all vertices in $V_1$ with color 1 and all vertices in $V_2$ with color 2. No two adjacent vertices will share the same color.

Since the graph is connected and has $n > 2$ vertices, it must contain at least one edge. A graph with at least one edge cannot be colored with $1$ color. Thus, the chromatic number is exactly $2$.

Hence, the correct option is A.