Partitionability to a tree and a spanning tree
When can the edge-set of an undirected graph be partitioned into a tree and a spanning tree?
The problem is NP-complete. The proof can be found in .
The problem of deciding whether the edge-set of an undirected graph is the union of k spanning trees or not is in P because of Tutte's disjoint tree theorem. It was shown by D. Pálvölgyi  that it is NP-complete to decide if the edge-set of a simple graph is the union of two disjoint - not necessarly spanning - trees.