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).