An undirected, unweighted, simple graph G(V, E) is said to be 2-colorable if there exists a function c: V \0, 1\ such that for every (u, v) E, c(u) 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| |V|), if G is represented as an adjacency list

Official 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 (|V| + |E|), if G is represented as an adjacency list. Explanation: A graph G is 2-colorable if and only if it is bipartite. - Odd Cycles: A fundamental property of bipartite (2-colorable) graphs is that they contain no odd cycles. Therefore, statement (A) is false. - Even Cycles: Bipartite graphs may contain cycles of even length (for example, a 4-cycle C4 is 2-colorable). Thus, statement (B) is true. - Algorithm Complexity: Testing whether a graph is bipartite (2-colorable) can be done using standard graph traversal (BFS or DFS) by assigning alternating colors level by level. With an adjacency list representation, this traversal visits every vertex and explores every edge, running in (|V| + |E|) time, which is optimal. Therefore, statement (C) is true and statement (D) is false.

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| |V|), if G is represented as an adjacency list

Algorithms · Graph Traversals

Official IIT answer key · IIT Roorkee · Audited Aug 2026

Take topic test

GATE CSE 2026 Set 1 Q55 · MSQ · 2 marks

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?

Select one or more options

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

GATE tests Graph Traversals (BFS and DFS) through deep theoretical properties rather than simple code tracing. Key emphases include edge classification (tree, back, forward, cross edges), timestamp intervals via the Parenthesis Theorem, DAG topological orderings, and structural invariants like the BFS level difference inequality and tree height versus graph diameter. Recent papers heavily favor MSQs and multi-property conceptual deductions over simple single-answer lookups.

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

Algorithms · Graph Traversals

Official IIT answer key · IIT Roorkee · Audited Aug 2026

Take topic test

GATE CSE 2026 Set 1 Q55 · MSQ · 2 marks

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?

Select one or more options

Key concept

Graph Traversals

Step-by-step verified solution

Examiner trap & misconception

Topic notes

How GATE tests Graph Traversals

Full Graph Traversals guide →

More on Graph Traversals

All 16 questions on Graph Traversals →

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.

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?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2026 Set 1

More on Graph Traversals

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?

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2026 Set 1

More on Graph Traversals

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2026 Set 1

More on Graph Traversals

Share this solution

Step-by-step verified solution

Check you can still solve Graph Traversals under a clock

More from GATE CSE 2026 Set 1

More on Graph Traversals

Share this solution