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.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
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?