Question

An undirected, unweighted, simple graph 𝐺(𝑉, 𝐸) is said to be 2-colorable if there
exists a function 𝑐: 𝑉→{0, 1} such that for every (𝑢, 𝑣) ∈𝐸, 𝑐(𝑢) ≠𝑐(𝑣).
Which of the following statements about 2-colorable graphs is/are true?

• A. If 𝐺 is 2-colorable, then 𝐺 may contain cycles of odd length
• B. If 𝐺 is 2-colorable, then 𝐺 may contain cycles of even length
• C. An optimal algorithm for testing whether 𝐺 is 2-colorable runs in time Θ(|𝑉| + |𝐸|), if 𝐺 is represented as an adjacency list
• D. An optimal algorithm for testing whether 𝐺 is 2-colorable runs in time Θ(|𝐸| log|𝑉|), if 𝐺 is represented as an adjacency list

Hint:

Recall that 2-colorable graphs are exactly the bipartite graphs, which never contain odd cycles but may contain even cycles, and can be tested optimally in \(\Theta(|V|+|E|)\) time using BFS/DFS on an adjacency list.

Answer 1

The Correct Option is B, C

A graph \(G\) is 2-colorable exactly when it is bipartite. We check each option using this fact together with the standard 2-coloring (BFS/DFS) algorithm.

Step 1: Odd cycles and bipartiteness.

A classical theorem states that a graph is bipartite (2-colorable) if and only if it has no cycle of odd length. If \(G\) contains an odd cycle \(v_1, v_2, ..., v_{2k+1}, v_1\), then coloring alternately forces \(c(v_1) \neq c(v_2) \neq ... \neq c(v_{2k+1})\), but since the cycle length is odd, \(v_1\) and \(v_{2k+1}\) end up needing the same color, and they are adjacent - a contradiction. So a 2-colorable graph can never contain an odd cycle. Statement A (may contain odd cycles) is false.

Step 2: Even cycles and bipartiteness.

Even cycles are perfectly consistent with 2-colorability. For example, a single 4-cycle \(v_1 - v_2 - v_3 - v_4 - v_1\) can be colored \(0,1,0,1\) with no conflict. So a 2-colorable graph may indeed contain even cycles. Statement B is true.

Step 3: Complexity of testing 2-colorability.

Testing whether \(G\) is 2-colorable is done by running BFS (or DFS) from every unvisited vertex, assigning colors alternately level by level, and checking every edge for a color conflict. With an adjacency list representation, each vertex is dequeued once and each edge is examined at most twice (once from each endpoint), giving total time \(\Theta(|V| + |E|)\). This is optimal since every vertex and edge must be inspected at least once. So statement C is true.

Step 4: Why \(\Theta(|E|\log|V|)\) is not correct.

A \(\log|V|\) factor arises in algorithms that need a priority queue (e.g., Dijkstra, Prim/Kruskal with heaps), not in a simple BFS/DFS traversal. Since 2-coloring needs no such ordering, claiming \(\Theta(|E|\log|V|)\) as the optimal bound is wrong - a faster linear algorithm already exists. Statement D is false.

Final Answer:

\[\boxed{\text{Options B and C are correct}}\]