Q45

MSQ2 marks

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)

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

Loading…