# Hardness of $2$ edge-disjoint spanning trees decomposition

The question is clear from the title. What is the complexity of the following decision problem:

Input: An undirected graph $$G(V, E)$$

Output: $$\mathrm{YES}$$ if $$G$$ can be decomposed into two edge-disjoint spanning trees, $$\mathrm{NO}$$ otherwise

## 1 Answer

Your problem is in $\mathrm{NP} \cap \mathrm{co}$-$\mathrm{NP}$.

First, it is obviously in $\mathrm{NP}$. The verifier receives the certificate consisting of two edge-disjoint spanning trees that consumes all the edges in $\mathrm{E}$

Second, by Tutte & Nash-Williams theorem , your problem is also in $\mathrm{co}$-$\mathrm{NP}$. The co-nondeterministic machine guesses any partition $\mathrm{P}$ of $\mathrm{V}$ and check that $|\mathrm{E}_\mathrm{P}(\mathrm{G})| \geq 2(|\mathrm{P}| - 1)$. Also, it must check that $|\mathrm{E}| = 2(|\mathrm{V}| - 1)$ to be sure that the tree packing of the above theorem is indeed a decomposition by trees.

 Tomas Kaiser, A short proof of the tree-packing theorem, https://arxiv.org/pdf/0911.2809.pdf