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.
