Question

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 \(\Theta(|V|+|E|)\), if \(G\) is represented as an adjacency list
• D. An optimal algorithm for testing whether \(G\) is 2-colorable runs in time \(\Theta(|E|\log|V|)\), if \(G\) is represented as an adjacency list

Hint:

Bipartite graphs never contain odd cycles but can contain even cycles; testing bipartiteness with BFS/DFS on an adjacency list runs in linear time \(\Theta(|V|+|E|)\), which is already optimal.

Answer 1

The Correct Option is B, C

Step 1: A 2-colorable graph is another name for a bipartite graph, one whose vertex set splits into two independent sets with all edges crossing between them.

Step 2: Parity argument for cycles. Walk around any cycle and flip color at every step. After an odd number of steps the color is opposite to where you started, after an even number of steps it matches. A cycle only closes up consistently (last vertex adjacent to first with opposite colors) when the number of edges, i.e. the cycle length, is even. So odd cycles are forbidden in a 2-colorable graph, ruling out option A.

Step 3: Concrete example for even cycles. The 4-cycle with alternating colors 0-1-0-1 is a valid 2-coloring, so even cycles are possible, confirming option B.

Step 4: Lower bound argument for the algorithm's complexity. Any algorithm that decides 2-colorability must look at every edge, because skipping an edge means you cannot rule out that edge being monochromatic under the color assignment you found; this gives an \(\Omega(|E|)\) lower bound, and combined with needing to visit every vertex, an \(\Omega(|V|+|E|)\) lower bound. BFS/DFS coloring achieves this bound exactly with an adjacency list, using \(O(1)\) work per edge and per vertex, so \(\Theta(|V|+|E|)\) matches the lower bound and is optimal, confirming option C.

Step 5: Since option C already gives an optimal \(\Theta(|V|+|E|)\) algorithm, any algorithm with a strictly larger growth rate such as \(\Theta(|E|\log|V|)\) cannot also be called optimal, so option D is false.

\[ \boxed{\text{B and C}} \]