Take the 2-minute tour ×
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|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
Dear Flo, hmm the way I thought about it is that the trees are not rooted and are directed in an arbitrary way. So the initial condition just say that D is the union of two spanning trees (when we forget about how the edges are directed,) and the conjecture is that, when we remember again the way the edges are directed, then unless we have a cut consisting just of two edges with reverse directions, we can actualy find two edge disjoint trees that reversing the direction in one lead to a strongly connected graph. So I thought about your version 2. –  Gil Kalai Jun 9 '12 at 21:39

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.