Computer Sciences > GATE 2026 SET-1 > Graph Algorithms
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| log|V|), if G is represented as an adjacency list

Correct : b,c

Similar Questions

Let G(V,E) be an undirected and unweighted graph with 100 vertices. Let d(u,v) denote the number of edges in a shortest path between vertices u and v in V. Let...
#1386 MCQ
Let G be an edge-weighted undirected graph with positive edge weights. Suppose a positive constant a is added to the weight of every edge. Which ONE of the foll...
#1445 MCQ
Consider the following algorithm someAlgo that takes an undirected graph G as input. The output of someAlgo (T) for the tree shown in the given figure is _____...
#1466 NAT

Related Topics

No tags found

Unique Visitor Count

Total Unique Visitors

Loading......

Question Options

Contributed by: