# Proof that a graph is 5-colorable

So I had an exam today and one of the questions were:

G is an undirected graph, and every two of its odd-lengthed cycles have a common vertex. Prove that G is 5-colorable.

So I found this answer (which is very annoying in its simplicity and elegance): 5-color graph problem

But I would like to write what I said in the exam, and hopefully someone can reassure me, because as things stand now - I'm pretty sure I did wrong.

I said: let's remove all of the edges of the odd-lengthed cycles from G (or one of its connected components, doesn't matter). This leaves only even-lengthed cycles and simple paths, which are both 2-colorable (even when connected). Also, any odd-lengthed cycle is 3-colorable, and any "connected" odd-lengthed cycles (with a common vertex) are also 3-colorable with the same 3 colors (just start from the connected vertex and continue alternatingly). So we return the edges of the odd-lengthed cycles to the original graph, and color their vertices with 3 new colors. So we have the 2 colors from when we removed the cycles, plus the three new colors that we added.

I think I'm wrong, or at least incomplete, because I don't really show that when I return all the edges, I'm not ruining the 3+2 colors somehow.. I don't know. If anyone could either disprove or reassure me that would be great (the latter would be greater).

Thanks!

• I don't really see your point. But two odd cycles can have many common vertices. There is nothing in the problem statement that says they have only one. Also if you have added back cycles $A$ and $B$, cycle $C$ may have several vertices in common with $A$ and several (possibly other ones) with $B$. In general there is no way you can consistently apply a 3-coloring. – Leen Droogendijk Jun 25 '14 at 14:59