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?

  • $\begingroup$ 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. $\endgroup$ – Justin Benfield Mar 13 '16 at 22:53
  • $\begingroup$ Must the two odd cyles share a unique vertex? Could there be two possible vertex that are common in the cycles? $\endgroup$ – kenny Mar 13 '16 at 23:02
  • $\begingroup$ When you remove $C$ every odd cycle becomes a path in $G-C$. Paths are no obstruction to bipartiteness. $\endgroup$ – Justin Benfield Mar 13 '16 at 23:05
  • $\begingroup$ I understand! If you want,, you can create an answer and I'll accept it. Thanks for your help $\endgroup$ – kenny Mar 13 '16 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.