# Making the union of two directed spanning trees strongly connected

Let *D=(V,E)* be a directed graph that is the union of two disjoint directed spanning trees. Can we characterize when does *D* have a directed spanning tree [math]T \subseteq E[/math] such that *E-T* is also a directed spanning tree and reversing the orientation of each edge of *T* results in a strongly connected digraph?

## Remarks

The condition that no cut consists of a pair of oppositely directed edges is clearly necessary for the existence of a directed tree with the prescribed properties. Gil Kalai proposed that this may also be sufficient, but a counterexample was found by Maria Chudnovsky and Paul Seymour, see the figure.

More generally, they gave the following additional necessary condition:

- There is no induced cycle of even length such that the arcs of the cycle alternate in direction, each node of the cycle is cubic, and none of them is a source or sink.

An obvious sufficient condition is that *D* is rooted 2-arc-connected from some root *r*, since then it decomposes into 2 *r*-arborescences by Edmonds' disjoint arborescences theorem, and the reversal of one of them results in a strongly connected digraph.