0
$\begingroup$

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?

$\endgroup$
4
  • $\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$ Mar 13, 2016 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$
    – user319202
    Mar 13, 2016 at 23:02
  • $\begingroup$ When you remove $C$ every odd cycle becomes a path in $G-C$. Paths are no obstruction to bipartiteness. $\endgroup$ Mar 13, 2016 at 23:05
  • $\begingroup$ I understand! If you want,, you can create an answer and I'll accept it. Thanks for your help $\endgroup$
    – user319202
    Mar 13, 2016 at 23:19

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .