If $G$ is 2-colorable, then $G$ may contain cycles of odd length

If $G$ is 2 -colorable, then $G$ may contain cycles of even length

An optimal algorithm for testing whether $G$ is 2-colorable runs in time $\theta(|V|+|E|)$, if $G$ is represented as an adjacency list

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

If $(\{P, Q\} \rightarrow\{R\}$ and $\{P\} \rightarrow\{R\})$, then $\{Q\} \rightarrow\{R\}$

If $\{P, Q\} \rightarrow\{R\}$, then $(\{P\} \rightarrow\{R\}$ or $\{Q\} \rightarrow\{R\})$

If $(\{P\} \rightarrow\{R\}$ and $\{Q\} \rightarrow\{S\})$, then $\{P, Q\} \rightarrow\{R, S\}$

If $\{P\} \rightarrow\{R\}$, then $\{P, Q\} \rightarrow\{R\}$

It is always possible to obtain a dependency-preserving 3NF decomposition of a relation

It is always possible to obtain a dependency-preserving 1NF decomposition of a relation

It is not always possible to obtain a dependency-preserving BCNF decomposition of a relation

It is not always possible to obtain a dependency-preserving 2NF decomposition of a relation