GATE CS 2026 Set 1 Q.55: Graph Traversals, Topological Sort and Connectivity

An undirected, unweighted, simple graph $G(V, E)$ is said to be 2-colorable if there exists a function $c: V \rightarrow \{0, 1\}$ such that for every $(u, v) \in E$ , $c(u) \neq c(v)$ .

Which of the following statements about 2-colorable graphs is/are true?

If $G$ is 2-colorable, then $G$ may contain cycles of odd length

If $G$ is 2-colorable, then $G$ may contain cycles of even length

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|V| + |E|)$ , if $G$ is represented as an adjacency list

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\Theta(|E| \log|V|)$ , if $G$ is represented as an adjacency list

Official answer and solution

Official answer: B and C
From: Official GATE 2026 answer key

Solution

Use the characterization of 2-colorable (bipartite) graphs and the linear time complexity of BFS/DFS 2-coloring.

A graph $G(V, E)$ is 2-colorable if and only if it is bipartite, which holds if and only if $G$ contains no cycles of odd length:

Option (A) is false and Option (B) is true: A 2-colorable graph can never contain an odd cycle, but may contain cycles of even length (e.g., $C_4$ ).
Option (C) is true and Option (D) is false: Running BFS or DFS on an adjacency list while greedily assigning alternating colors to neighbors tests 2-colorability in optimal $\Theta(|V| + |E|)$ time.

Final answer

Options (B), (C)

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2026 Computer Science and Information Technology - Session 1 (CS1)
Question: 55 of 65
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source