[Math] Proof that a graph is 5-colorable

Question

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!

Answer 1

Your 'proof' would show that any graph is 5-colorable. You found the weakness already: you cannot just 'independently' add back the old cycles: they will interfere.