GATE 2026 CS (CS1) – Question 55
An undirected, unweighted, simple graph $G(V, E)$ is said to be 2-colorable if there exists a function $c: V \to \{0, 1\}$ such that for every $(u, v) \in E$, $c(u) \ne c(v)$. Which of the following statements about 2-colorable graphs is/are true?
Practise this question in The GATE Grind →
Show answer and explanation
Correct answer: (B) If $G$ is 2-colorable, then $G$ may contain cycles of even length; (C) An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|V| + |E|)$, if $G$ is represented as an adjacency list
Explanation
A graph is 2-colorable if and only if it is **bipartite**.
- By König's theorem, a graph is bipartite (2-colorable) if and only if it contains **no odd cycles**. Thus, statement (A) is false.
- Bipartite graphs can certainly contain cycles of even length (e.g. $C_4, C_6, \dots$). Thus, statement (B) is true.
- 2-colorability can be tested by running a standard Breadth-First Search (BFS) or Depth-First Search (DFS) that colors vertices alternatively with two colors and checks for conflicts. With an adjacency list representation, BFS/DFS traverses every vertex and edge in linear time $\Theta(|V| + |E|)$. This is optimal since every vertex and edge must be inspected. Thus, statement (C) is true and (D) is false.
Therefore, statements (B) and (C) are true.