I am working on the following exercise:

> Consider a simple and connected undirected graph $G(V,E)$. Show that one can colour the edges of $G$ in polynomial time and with as few colours as possible such that there is no monochromatic cycle in said colouring of $G$.


EDIT: OK, my approach turned out to be false. I will leave it here for the sake of completeness. Now I have no idea how to solve this exercise. I guess the following theorem might be helpful:

> Theorem: For any undirected simple graph $G(V,E)$ we can decide whether the [edge chromatic number][1] is less than $3$ and if yes we can find this optimal colouring in linear time.














_________________________________________________________________________
My WRONG approach:

I think that 2 colours should be sufficient. (Remember that this is not the classical edge colouring problem, we just want to avoid monochromatic cycles.) My first idea is to formulate a simple greedy algorithm:

 1. Colour all edges in red.
 2. Check the graph for cycles. If there is a cycle delete one edge of the cycle from the graph. Repeat this step until there are no more cycles in $G$.
 3. Colour the deleted edges in blue.

However, the problem with this approach is that the blue edges may form a cylce as the example below shows. While the example below can easily be fixed by recolouring two edges I am not sure if this fix works in general. Could you please give me a hint?[![enter image description here][2]][2]


  [1]: https://mathworld.wolfram.com/EdgeChromaticNumber.html
  [2]: https://i.sstatic.net/NbJbR.jpg