GATE 2026 CS1 Q.55: solution and answer

GATE 2026 · CS1Q.55 · 2 marks · MSQ

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) \neq = c (v)$ .

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

(A)
If $G$ is 2-colorable, then $G$ may contain cycles of odd length
(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 $Θ (∣ V ∣ + ∣ E ∣)$ , if $G$ is represented as an adjacency list
(D)
An optimal algorithm for testing whether $G$ is 2-colorable runs in time $Θ (∣ E ∣ lo g ∣ V ∣)$ , if $G$ is represented as an adjacency list

See the question in the paper

Tap to open full size

Answer and solution

ANSWER

Statements (B) and (C) are true; (A) and (D) are false.

Official answer: B, CSource: Official answer key, GATE 2026 CS1 (IIT Guwahati)

Restate the theorem: a graph is 2-colorable (admits a proper coloring with 2 colors) if and only if it is bipartite, if and only if it contains no cycle of odd length.
Check (A): if $G$ contained an odd-length cycle, traversing the cycle and alternating colors 0,1,0,1,... would force the last vertex back to color 0, which is adjacent to the starting vertex also colored 0 — violating $c (u) \neq = c (v)$ on that edge. Hence a 2-colorable graph can never contain an odd cycle, so (A) is false.
Check (B): a 2-colorable graph can contain even-length cycles — for instance $C_{4}$ (a 4-cycle) admits the coloring $0, 1, 0, 1$ around the cycle, which is a valid 2-coloring. So (B) is true.
Check (C): a single BFS or DFS from each uncolored vertex, assigning the opposite color to each newly discovered neighbor and checking every edge for a same-color violation, visits every vertex once and examines every edge a constant number of times, giving $Θ (∣ V ∣ + ∣ E ∣)$ time on an adjacency-list representation. Since any correct algorithm must read the whole input (every vertex and edge) at least once, $Ω (∣ V ∣ + ∣ E ∣)$ is a lower bound, so this algorithm is optimal. Hence (C) is true.
Check (D): $Θ (∣ E ∣ lo g ∣ V ∣)$ is asymptotically worse than the achievable and optimal $Θ (∣ V ∣ + ∣ E ∣)$ bound (whenever $∣ V ∣ \geq 2$ ), so it cannot describe an optimal algorithm's running time. Hence (D) is false.
Conclusion: the true statements are (B) and (C).

KEY IDEA

2-colorability of a graph is exactly bipartiteness, and bipartiteness is testable in linear time by a single BFS/DFS coloring pass.

WATCH OUT FOR

Confusing "2-colorable" with "properly colored graphs can have any cycle type" — a bipartite (2-colorable) graph can never contain an odd cycle, since traversing an odd cycle forces two adjacent vertices to receive the same color; students sometimes pick (A) by only checking small examples instead of proving the general impossibility.

From the GATE 2026 CS1 paper. Every question of this paper · Download the full paper · All 28 Graph algorithms questions, with notes

GATE 2026 CS1 Q.55: solution and answer

Answer and solution

More Graph algorithms questions