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: Understand what 2-colorable means.
A graph \(G(V,E)\) is 2-colorable if its vertices split into two sets \(V_0\) and \(V_1\) (colors 0 and 1) so that every edge has one endpoint in each set. This is exactly the definition of a bipartite graph.

Step 2: Check statement A, can a 2-colorable graph contain an odd cycle.
Take any cycle \(v_1, v_2, \ldots, v_k, v_1\) in \(G\). Consecutive vertices on the cycle are joined by an edge, so colors must alternate along the cycle: \(c(v_1) \neq c(v_2) \neq c(v_3) \ldots\). Walking all the way around, the color returns to \(c(v_1)\) only if \(k\) is even. If \(k\) is odd, the closing edge \((v_k, v_1)\) forces \(c(v_k) = c(v_1)\), which breaks the requirement \(c(v_k) \neq c(v_1)\). So a 2-colorable graph can never contain an odd cycle, and statement A is false.

Step 3: Check statement B, can a 2-colorable graph contain an even cycle.
Take the 4-cycle \(v_1\text{-}v_2\text{-}v_3\text{-}v_4\text{-}v_1\) and color \(v_1,v_3\) with 0 and \(v_2,v_4\) with 1. Every edge joins a 0-colored vertex to a 1-colored vertex, so this graph is 2-colorable and contains an even cycle. Any even cycle admits this alternating coloring, so statement B is true.

Step 4: Check statement C, complexity of testing 2-colorability.
Testing 2-colorability is the same as testing bipartiteness. The standard algorithm runs BFS or DFS from every uncolored vertex, coloring each visited vertex opposite to its parent, and reports failure the moment an edge joins two same-colored vertices. With an adjacency list, BFS/DFS visits every vertex once and scans every edge at most twice (once from each endpoint), giving \(\Theta(|V|+|E|)\) time. Any correct algorithm must examine every edge at least once, since an unexamined edge could be the one that breaks bipartiteness, so \(\Theta(|V|+|E|)\) is asymptotically optimal. Statement C is true.

Step 5: Check statement D.
\(\Theta(|E|\log|V|)\) is asymptotically slower than \(\Theta(|V|+|E|)\) once \(|V|>2\), because \(\log|V|\) grows without bound while a constant factor does not. Since the faster correct BFS/DFS algorithm from Step 4 already exists, an algorithm running in \(\Theta(|E|\log|V|)\) is not optimal. Statement D is false.

Step 6: Conclusion, the true statements are B and C.

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