[Math] Understanding pairs of odd cycles can 5 colour a graph

coloringgraph theory

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?

Best Answer

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.

Related Question