edges in at most one odd cycle, 3 colorable Prove that if $G$ is a graph in which every edge is a part of at most one odd length cycle, then the graph is 3 colorable.
I want to show that if a graph is 4-critical there are two odd cycles which share an edge, which would prove the question. I'm not sure how to get that. I thought to take a maximum path, and then an end point has at least 3 neighbours in the path, which ensures 3 cycles, but I don't see a reason they can't all be even.
 A: Here are some hints that lead to a proof.
Show that a 2-connected graph in which every edge is on at most one odd cycle is either bipartite or an odd cycle (e.g. by using an ear decomposition).
Show that the chromatic number of a graph equals the maximum of the chromatic numbers of its blocks.
As an alternative for the second part: use induction on the number of vertices.
If $G$ is 2-connected we proved it in the first part. Otherwise $G$ has a cut vertex $v$.
For a component $C$ of $G-v$ show that the conditions of the problem hold in $C+v$ (since cycles must be contained completely in one such enhanced component). So you can use the induction hypothesis on each such component ($+v$) and glue them together (you can always make sure that $v$ has color 1 in each of them).
A: You can use induction on the number of odd cycles in G.  
Assume that number is 0.  Then G is bipartite and so 3-colorable.
For the induction step, assume G has k+1 odd cycles.  Remove an edge $e=(u,v)$ that belongs to one of the odd cycles.  So, $G-e$ contains $k$ odd cycles with every edge belonging to at most one of them, and so can be 3-colored.  Let $f$ be such a coloring of $G$.
Now, we try to add $e$ to $G$. If $f(u)\neq f(v)$ then $e$ can be safely added back to $G$.  Else, assume w.l.o.g that $f(v)=f(u)=1$, and define $G_{ij}$, for $i<j\in {1,2,3}$ to be the sub-graph of $G$ containing only vertices whose color in $f$ is $i$ or $j$.  Note that in every connected component of $G_{ij}$ it is possible to switch the color of every vertex while still having a legal coloring.  So, if $u,v$ belong to different connected components of $G_{12}$ or $G_{13}$ the color of one of them can be changed, allowing $e$ to be added safely back to the graph.
If this is not the case, than $u,v$ belong to the same connected component in both $G_{12}, G_{13}$.  So, there is a path $p_1:u\rightsquigarrow v$ in $G_{12}$ with all vertices colored 1 or 2.  Note that since $u,v$ are colored 1, the path must be of even length.  In the same manner, there is an even length path $p_2:u\rightsquigarrow v$ with all vertices colored only in 1 and 3. Clearly, $p_1,p_2$ are edge-disjoint.  For each of these paths, the edge $e=(u,v)$ closes an odd-length cycle, and so $e$ belongs to two odd-length cycle, in contradiction to the assumption that it belongs to at most one.  
A: As so often in graph theory, we can attempt a proof by looking for a minimal counter-example.
Let $G(V,E)$ be a graph where every edge is part of at most one odd cycle.
Let $\mathcal C$ be the set of all valid colurings $c\colon V\to\{1,\ldots,\chi(G)\}$.
Let $m=\min\{\,|c^{-1}(1)|:c\in\mathcal C\,\}$ and $\mathcal C_1=\{\,c\in\mathcal C:|c^{-1}(1)|=m\,\}$. Pick $c_1\in\mathcal C_1$ and $v_1\in c_1^{-1}(1)$ (which is possible because $m>0$ by definition of $\chi$).
For $c\in\mathcal C_1$ let $f(c)=|\{\,u\in c^{-1}(2):v_1u\in E\,\}|$.
Let $n=\min\{\,f(c):c\in \mathcal C_1\,\}$. Let $\mathcal C_2=\{\,c\in\mathcal C_1:f(c)=n\,\}$ and pick $c_2\in\mathcal C_2$.
Then $n>0$ because otherwise $\tilde c\colon v\mapsto\begin{cases}2&\text{if $v=v_1$}\\c_2(v)&\text{otherwise}\end{cases}$ would be a colouring with $|\tilde c^{-1}(1)|<m$.
Thus we can pick $v_2$ with $v_1v_2\in E $ and $c_2(v_2)=2$.
Let $v_3$ be a neighbour of $v_1$ with $c_2(v_3)\ne 2$ and assume there is a path from $v_2$ to $v_3$ using only vertices of colours $2$ and $c_2(v_3)$. Then this path together with $v_3v_1$ and $v_1v_2$ is an odd cycle containg $v_1v_2$. By assumption, there can be at most one such neighbour $v_3$. Let $a=c(v_3)$ if such $v_3$ exists, otherwise let $a=3$.
Assume there exists $b\in\{1,\ldots,\chi(G)\}\setminus\{1,2,a\}$. Consider the subgraph $(V,\{uw\in E: \{c_2(u),c_2(w)\}=\{2,b\}\})$ of $G$ amd let $H$ be the connected component of $v_2$ in it.
Then $$ \hat c(v)=\begin{cases}b+2-c_2(v)&\text{if $v\in H$}\\c_2(v)&\text{otherwise}\end{cases}$$
is a valid colouring, is $\in\mathcal C_1$ and has $f(\hat c)<n$, contradiction.
Therefore the assumpotion that $b$ as above exists mus be wrong. We conclude that $\chi(G)\le 3$.
