# Let $G$ be a graph with the property: for any odd cycles $C_1, C_2$ of graph $G$, it holds that $V(C_1) \cap V(C_2) \neq \emptyset$.

Let $$G$$ be a graph with the property: for any odd cycles $$C_1, C_2$$ of graph $$G$$, it holds that $$V(C_1) \cap V(C_2) \neq \emptyset$$.

(a) Let $$C$$ be an odd cycle in graph $$G$$. Prove that $$\chi(G - V(C)) \leq 2$$.

(b) Prove that $$\chi(G) \leq 5$$.

Attempt:

(a) To prove that $$\chi(G - V(C)) \leq 2$$, we need to show that the chromatic number of the graph resulting from removing the vertices of any odd cycle $$C$$ from $$G$$ is at most 2. Given $$C$$, let $$G' = G - V(C)$$ be the graph obtained by removing the vertices of $$C$$ from $$G$$. We aim to show that $$\chi(G') \leq 2$$.

Since $$C$$ is an odd cycle, $$G'$$ remains connected because the removal of $$V(C)$$ cannot disconnect $$G$$ due to the given property that any pair of odd cycles in $$G$$ share at least one vertex.

Now, I consider a maximal path $$P$$ in $$G'$$. Since $$P$$ is a path, its endpoints are of degree 1 in $$G'$$. Now I suppose $$P$$ has length $$k$$. Since $$P$$ is maximal, the neighbors of the endpoints of $$P$$ must all lie on $$P$$. Because $$P$$ is a path, each of its vertices has at most two neighbors on $$P$$.

Have I started o. k.? Is this the right path?

(b) To prove that $$\chi(G) \leq 5$$, where $$\chi(G)$$ denotes the chromatic number of the graph $$G$$, I use a proof by contradiction. I assume, for the sake of contradiction, that $$\chi(G) > 5$$. This implies that there exists a coloring of $$G$$ using at least $$6$$ colors. Let $$c: V(G) \rightarrow {1, 2, 3, 4, 5, 6}$$ be such a coloring.

Now I consider the induced subgraph $$G_i$$ of $$G$$ consisting of all vertices colored with color $$i$$, for $$i = 1, 2, 3, 4, 5, 6$$. Since $$\chi(G) > 5$$, at least one of these induced subgraphs, say $$G_6$$, must be non-empty. Since $$G_6$$ is non-empty, it must contain at least one vertex, say $$v$$. Now, consider the neighborhood of $$v$$ in $$G$$, denoted as $$N(v)$$. Since $$G_6$$ is an induced subgraph, all vertices in $$N(v)$$ must be colored with colors other than $$6$$.

I have the same questions as above ... And help would be appreciated.

• Your proof by contradiction approach looks valid - it is fairly standard for graph-theory problems. I am just wondering (no success yet) whether part (a) has a simpler proof. If I find one I will add it as an answer. Commented Apr 30 at 0:20
• @RedFive I raised an objection to OP's proof by contradiction for (a). Can you review it and see what I missed? Commented Apr 30 at 1:08
• Will do when I get a chance. Quite interesting. You may not have missed anything, so I will check carefully. Commented Apr 30 at 1:28

• For your writeup of (a), your initial claim of "the removal of $$V(C)$$ cannot disconnect $$G$$" is false.
• For (a), you can just do it directly. Show that any graph that has no odd cycles (hence only has even cycles) is a bipartite graph, and hence conclude $$\chi (G') \leq 2$$.
• For (b), Since $$G'$$ has chromatic number 2, use 2 colors. The odd cycle $$C$$ has chromatic number 3, so use 3 different colors. This is a 5 coloring of $$G$$ that is clearly chromatic, so $$\chi(G) \leq 5$$ (we might be able to do better).
• @RedFive My concern is only with the validity of the claim, which indicates that the rest of the proof is incorrect. Just because the conclusion of an incorrect proof is correct (via other means), doesn't mean that the proof is correct. We do not judge solutions only by the truth of the final statement. $\quad$ IE It is true that $\chi (G') \leq 2$(like I shown above), but it is still not true that "removal of $V(C)$ cannot disconnect $G$". Commented May 1 at 14:19