# 5-color graph problem

I need to demonstrate that a graph that doesn't have odd disjunctive circuits is a five color graph. This is indeed for a homework. I need some suggestions on how to approach this problem. Any help is welcomed.

-
I assume by "doesn't have odd disjunctive circuits" you that the graph "does not contain two vertex-disjoint odd circuits"? – Chris Godsil Jan 22 '13 at 22:23
and "is a five colour graph" means its vertices can be coloured with five colours in such a way that adjacent vertices have different colours? – Chris Eagle Jan 22 '13 at 22:26
@ChrisEagle Yes, that's what it means – Bogdan Jan 22 '13 at 22:29
@ChrisGodsil Yes, it doesn't contain two vertex-disjoint odd circuits – Bogdan Jan 22 '13 at 22:29

If there is an odd cycle, select a shortest one and remove all its vertices. The remaining graph is bipartite and can be coloured with $A$ and $B$. Put the removed cycle back in and colour it with $C$, $D$ and $E$. Why can there be no colour conflict?