Sign up ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?


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

share|cite|improve this question
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.