Suppose we have a graph whose edges are coloured. It's not necessarily a proper colouring: a given node may have 0, 1, or several incident edges of a given colour.

Is the following problem NP-complete? Determine whether there are two edge-disjoint spanning trees, such that in each individual tree, no colour appears twice.

I am curious because the variant "determine whether there are two edge-disjoint spanning trees, such that in the **union** of the trees, no colour appears twice" is solvable in polynomial time, for example using matroid theory.

onerainbow spanning tree using matroid intersection. Can you say a bit more about how to find two disjoint spanning trees whose union is rainbow? $\endgroup$ – Tony Huynh May 24 '10 at 23:05spanningtrees. Schrijver's book sections 51.4, 42.3 talks about polynomial-time algorithms for this (corrected) version. $\endgroup$ – Dave Pritchard May 26 '10 at 12:17