show/hide this revision's text 3 added 125 characters in body

Here are some nice lemmas that you can use: http://www.cs.elte.hu/egres/qp/egresqp-10-04.pdf

Dave pointed out my mistake, the subgraphs of spanning trees do not have to be trees. So I have no clue about the answer.

Espacially Problem 4 (or 10) seems promising. Take the graph from their construction such that all of its edges have a different color, suppose it has e edges. Then if we allow multigraphs, adding every edge with multiplicity 2n-2-e, all of a different color but same for each edge (thus in total we have 2n-2 colors) shows that your question solvable in P is NP-hard for multigraphs. Am I right? I would guess that with some further tricks you can make a simple graph from this for the variant you asked.
show/hide this revision's text 2 added 100 characters in body

Here are some nice lemmas that you can use: http://www.cs.elte.hu/egres/qp/egresqp-10-04.pdf

Espacially Problem 4 (or 10) seems promising. Take the graph from their construction such that all of its edges have a different color, suppose it has e edges. Then if we allow multigraphs, adding every remaining edge with multiplicity 2n-2-e, all of a different color but same for each new edge (thus in total we have 2n-2 colors) shows that your question solvable in P is NP-hard for multigraphs. RightAm I right? I would guess that with some further tricks you can make a simple graph from this for the variant you asked.
show/hide this revision's text 1

Here are some nice lemmas that you can use: http://www.cs.elte.hu/egres/qp/egresqp-10-04.pdf

Espacially Problem 4 (or 10) seems promising. Take the graph from their construction such that all of its edges have a different color, suppose it has e edges. Then if we allow multigraphs, adding every remaining edge with multiplicity 2n-2-e, all of a different color but same for each new edge (thus in total we have 2n-2 colors) shows that your question solvable in P is NP-hard for multigraphs. Right?