How to find two disjoint spanning trees of an undirected graph

Question

Is there any applicable approach to find two disjoint spanning trees of an undirected graph or to check if a certain graph has two disjoint spanning trees

Answer 1

This is an example of Matroid union. Consider the graphic matroid where the basis are given by the spanning trees. Now the union of this matroid with itself is again a matroid. Your question is about the size of the basis of this matroid. (whether there exist a basis of size $2(|V|-1)$.

The canonical algorithm for this is Matroid partitioning algorithm. There exist an algorithm which does does the following: It maintains a set of edges with a partitioning into two forests. At each step given a new edge $e$, it decides whether there exist a reshuffling of the current partition into a new partition such that the new edge can be added to the set and the partition remains independent. And if not, it somehow will provide a certificate that it cannot.

For details look at a course in Comb. Optimization or the book by Schriver.

Answer 2

Not sure it helps much in the applicable side but Tutte [1961a] and Nash-Williams [1961] independently characterized graphs having k pairwise edge-disjoint spanning trees:

A graph G has k pairwise edge-disjoint spanning trees iff for every partition of the vertices of G into r sets, there are at least k(r-1) edges of G whose endpoints are in different sets of the partition.

Use k=2 and it may give you a lead for your needs.