GATE CS 2026 Set 1 Q45 — Graphs: Connectivity, Matching, Colouring

A graph $G$ is $2$-colorable if and only if it is bipartite. Let us analyze each statement based on the properties of bipartite graphs:

• Statement A is False: A fundamental theorem in graph theory states that a graph is bipartite (2-colorable) if and only if it contains no odd cycles. Therefore, a $2$-colorable graph cannot contain any cycles of odd length.
• Statement B is True: A bipartite graph can contain cycles of even length. For example, the cycle graph $C_4$ (a square) is $2$-colorable and has an even length of $4$.
• Statement C is True & Statement D is False: We can test if a graph $G(V, E)$ is $2$-colorable using a standard graph traversal algorithm like Breadth-First Search (BFS) or Depth-First Search (DFS):
  1. Start traversing from an uncolored vertex, coloring it $0$.
  2. Color all its neighbors with $1$, their neighbors with $0$, and so on.
  3. If we ever find an edge connecting two vertices of the same color, the graph is not $2$-colorable.
  Since BFS/DFS visits each vertex and each edge a constant number of times, the time complexity using an adjacency list representation is $\Theta(|V| + |E|)$. This is optimal because any algorithm must examine every vertex and edge in the worst case to determine colorability.

Thus, the true statements are B and C.