This problem actually arose when designing a computer network.


Let $G=(V,E)$ be a finite, simple, undirected graph such that every vertex has degree at least $2$. Given $n\in\mathbb{N}$, a map $c:E \to \{1,\ldots, n\}$ is said to be a *weak coloring* if for every $v\in V$ the edges adjacent to $v$ do not all have the same color. (More formally, we want the restriction $c|\_{E(v)}$ to be non-constant, where $E(v) = \{e\in E: x\in e\}$.)


Is there for every graph $G=(V,E)$ with minimal degree $2$ a weak edge coloring $c:E\to\{1,2\}$?



Different form of edge coloring
No. For a cycle $C\_n$ of odd length the condition is equivalent to bipartiteness of the line graph, which is itself $C\_n$ and is not bipartite, hence there is no weak coloring.


Odd cycles are the only counter-examples among connected graphs. To see that, suppose that there is a vertex $v$ of degree at least 3. Add edges of a matching $M$ to $G$ so that in the new graph $G'$ all vertices have even degree. Find an Euler tour in $G'$ starting at $v$ using an edge of $M$ if possible, and color edges of $E \cup M$ alternately in the order of this tour. We claim that the restriction of this coloring to $E$ is weak 2-coloring. If $u \neq v$ had odd degree, then the degree was at least 3, hence the tour visits $u$ at least twice, with adjacent edges having different colors, and deleting at most one edge of $M$ will leave at least one differently colored pair intact. If a vertex $u \neq v$ had even degree in $G$, then no edges incident to $u$ belong to $M$. $v$ has at least one pair of edges of $E$ adjacent in the tour, hence it will not be monochromatic in $E$.


