An undirected, unweighted, simple graph $G(V, E)$ is said to be 2-colorable if there exists a function $c: V \rightarrow \{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 graph $G$ is 2-colorable if and only if it is bipartite.

• Odd Cycles: A fundamental property of bipartite (2-colorable) graphs is that they contain no odd cycles. Therefore, statement (A) is false.

• Even Cycles: Bipartite graphs may contain cycles of even length (for example, a 4-cycle $C_4$ is 2-colorable). Thus, statement (B) is true.

• Algorithm Complexity: Testing whether a graph is bipartite (2-colorable) can be done using standard graph traversal (BFS or DFS) by assigning alternating colors level by level. With an adjacency list representation, this traversal visits every vertex and explores every edge, running in $\Theta(|V| + |E|)$ time, which is optimal. Therefore, statement (C) is true and statement (D) is false.