Prove that if G is a connected graph that is not an odd cycle, then it has an edge 2-coloring such that every vertex with degree at least two is adjacent to edges of both colors.
My own idea was to prove it by induction on the number of vertices, but the problem is that if we omit a vertex that all of its neighbors have degree two, then we might face a problem to complete the induction.
Best Answer
By a good coloring of a graph $G$ I mean a $2$-coloring of the edges with colors red and blue such that every vertex of degree at least $2$ is incident with a red edge and a blue edge.
Lemma. Let $G$ be a connected graph which is not an odd cycle. If $G$ has at most one vertex of degree different from $2$, then $G$ has a good coloring.
Proof. If all vertices of $G$ have degree $2$, then $G$ is an even cycle. If $G$ has just one vertex $v$ of degree different from $2$, then either $G=K_1$, or else $G$ consists of two or more cycles glued together at one vertex. (Note that $G$ is Eulerian, and consider the cycles traversed by an Euler circuit between successive visits to $v$.) In all these cases the existence of a good coloring is easily verified.
Theorem. Every connected graph which is not an odd cycle has a good coloring.
Proof. We use induction on the size of the graph, i.e., the number of edges. Let $G$ be a connected graph which is not an odd cycle, and assume that the theorem holds for all smaller graphs.
By the lemma, we may assume that $G$ has two distinct vertices, $u$ and $v$, whose degrees are different from $2$. Let $P$ be a path from $u$ to $v$. Color the edges of $P$ alternately red and blue.
Now consider the connected components of $G-E(P)$. Give each component which is not an odd cycle a good coloring, which exists by the inductive hypothesis. However, if any component $C$ of $G-E(P)$ is an odd cycle, then choose a vertex $w\in V(C)\cap V(P)$, and color the edges of $C$ alternately red and blue, except that the two edges incident with $w$ shall have the same color, and if $w$ happens to be an end vertex of $P$, that color shall be different from the color of the edge of $P$ which is incident with $w$.
It is easy to see that this is a good coloring of $G$.