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?

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

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

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

GATE CSE 2026 Session 1 Q55: Properties of 2-colorable (bipartite) graphs

Algorithms
2 marks
MSQ
No negative marking

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?

Try it: multiple select: one or more correct options

Select all correct options. No negative marking, no partial marks.

Show answer and explanation

Answer: B, C (official GATE 2026 final answer key)

Concept used: A graph is bipartite iff it has no odd cycle; BFS/DFS 2-colouring tests this in linear time.

First step: Colour a BFS tree by level parity and check every edge joins different colours.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2026 Session 1 CS question paper and final answer key, organised by IIT Guwahati. Question paper · Answer key

PracticePractise Algorithms questions →Full paperAll GATE CSE 2026 Session 1 questions →

GATE CSE 2026 Session 1 Q55: Properties of 2-colorable (bipartite) graphs

Question

Full step-by-step solution

More Algorithms PYQs