How to avoid monochromatic cycles?

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 1: 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 is less than $$3$$ and if yes we can find this optimal colouring in polynomial time.

EDIT 2: I have reread my lecture notes. This exercise is probably meant to be solved with tools from matroid theory. I just do not see how.

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?

• Deciding whether a given directed graph can be vertex partitioned into two acyclic subgraphs [is][1] $\text{NP}$-complete. So we know the problem is hard for directed graphs. Why you think it is easier for undirected ones? Did I miss something?! [1]: feb.kuleuven.be/public/u0004371/published%20papers/… – Bader Abu Radi Jan 21 at 17:55
• @BaderAbuRadi The reference you shared is for the vertex coloring. It is not for the edge coloring. :) – Inuyasha Yagami Jan 21 at 18:03
• @Inuyashayagami Oh, I see. Thanks. – Bader Abu Radi Jan 21 at 18:05
• I will make an edit to the question. – 3nondatur Jan 21 at 18:07