Here a proof I am trying to make sense of.
Let G be a graph in which each pair of odd cycles shares a common
vertex. Show that χ(G)≤5.
Let C be any odd cycle of G (if none exists, let C=∅).
Since each odd cycle of G shared a vertex with C, we see that
G−C has no odd cycles. Therefore G−C is bipartite and hence
2-colorable. The vertices of C can be colored with 3 new colors,
so we can color G with 5 colors. Therefore χ(G)≤5.
If the number of vertices be even, can't G−C become an odd cycle as well, therefore it cannot become a bipartite? I'm tripped by this fact that. What typical constraints does the G−C must have in order for this property to be true? Planarity? There must exists a odd cycle of 3 or 5 in the graph then.
Could someone clarify some ambiguities with this simple proof?
