# Partitionability to a tree and a spanning tree

From Egres Open

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 ^{[1]}.

## Remarks

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 ^{[2]} 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.

## References

- ↑ A. Bernáth, Z. Király:
*Finding edge-disjoint subgraphs in graphs*, EGRES Quick Proofs QP-2010-04. - ↑ D. Pálvölgyi:
*Partitionability to two trees is NP-complete*, EGRES Quick Proofs QP-2006-06.