Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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
up vote 0 down vote accepted

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?

share|cite|improve this answer
Is it because the shortest odd cycle is made out of 3 vertices and that cycle can be colored with 3 colors different from the 2 colored remaining bipartite graph? – Bogdan Jan 22 '13 at 23:01

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.