Problem of the month March 2010

The problem for this month is not of central importance, but it is one of those simple natural problems that we feel should be settled. It is the following question on edge-disjoint spanning trees and paths:

When does an undirected graph, with given nodes s and t, contain k spanning trees and l s-t paths, all of which are edge-disjoint?

The only case we know is k=l=1, but probably it is not hard to obtain other partial results, so do not hesitate to add your observations on the discussion page of the problem!

The problem is NP-complete even for k=l=1, see the problem page.