A K-colouring of an undirected graph G = (V, E) is a function c : V → {0, 1, …, K − 1} such that c(u) ≠ c(v) for every edge (u, v) ∈ E. For a 2-colourable graph G, which of the following is not correct?

1. AG is bipartite
2. BG is 2-colorable
3. CG has cycles of odd length
4. DG has no cycles of odd length

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: C. G has cycles of odd length

Explanation

2-colourable ⇔ bipartite ⇔ no odd cycle. So 'G has cycles of odd length' is the incorrect statement.