# Understanding pairs of odd cycles can 5 colour a graph

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 $\chi(G)\leq 5$.

Let $C$ be any odd cycle of $G$ (if none exists, let $C=\emptyset$). 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 $\chi(G)\leq 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?

• Note that each pair of odd cycles share a vertex. Since this is so, removing $C$ removes a vertex from every odd cycle. Thus $G-C$ comprises only even cycles. Commented Mar 13, 2016 at 22:53
• Must the two odd cyles share a unique vertex? Could there be two possible vertex that are common in the cycles? Commented Mar 13, 2016 at 23:02
• When you remove $C$ every odd cycle becomes a path in $G-C$. Paths are no obstruction to bipartiteness. Commented Mar 13, 2016 at 23:05
• I understand! If you want,, you can create an answer and I'll accept it. Thanks for your help Commented Mar 13, 2016 at 23:19

There are two key observations to make: First, the hypothesis is that each pair of odd cycles share a vertex. This includes the pair $C,K$ for every $K$ an odd cycle in $G$. Hence when we remove $C$ from $G$, each odd cycle loses a vertex, and this is where the second key observation comes in: cutting a vertex from a cycle leaves a path, and paths are no obstruction to being bipartite.