# A Conjecture About Directed Graphs that are the Union of Two Trees

Let D=(V,E) be a directed graph that is the union of two edge-disjoint directed spanning trees. Suppose that

There no subset X of vertices so that there is precisely one directed edge from X to its complement and one directed edge from the complement of X to X.

Is it true that D has a directed spanning tree T, T is a subset of E, 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?

### update:

The answer is NO as pointed out by an example by Maria Chudnovsky and Paul Seymour, who also pointed out additional necessary conditions. A remaining question is:

Problem: Find a characterization of directed graphs $D$ that has a spanning tree $T$, such that $E-T$ is also a spanning tree and reversing the orientation of each edge of $T$ results in a strongly connected digraph

• I wonder if anyone else has also spent the last 2 hours attempting counterexamples :( – Vidit Nanda Jun 5 '12 at 22:05
• Should the two directed spanning trees comprising D have the same root? – Benjamin Young Jun 7 '12 at 16:38
• Dear Benjamin, not at all. – Gil Kalai Jun 7 '12 at 19:28
• Gil, when you say "directed trees", do you mean 1) rooted tree, and all edges directed away from it, or 2) tree with all edges directed some way? – Flo Pfender Jun 8 '12 at 8:04
• Where is the example of Chudnovsky & Seymour? – Gerry Myerson Aug 12 '14 at 1:42