Prove that if a graph does not have two disjoint odd cycles then χ(G) ≤ 5, where χ(G) denotes the minimum number of colors needed to color the vertices of G. χ(G) is the chromatic number of G.
Intuitions:
It is clear that any odd-cycle must have a chromatic number of 3. Each clique of the graph that has an odd-cycle must thus have a chromatic number of three, but I don't see how this helps the proof.
On a related note: would it be easier to prove the contrapositive or use a proof by contradiction?
For self-study.