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

  • 3
    $\begingroup$ I wonder if anyone else has also spent the last 2 hours attempting counterexamples :( $\endgroup$ – Vidit Nanda Jun 5 '12 at 22:05
  • $\begingroup$ Should the two directed spanning trees comprising D have the same root? $\endgroup$ – Benjamin Young Jun 7 '12 at 16:38
  • $\begingroup$ Dear Benjamin, not at all. $\endgroup$ – Gil Kalai Jun 7 '12 at 19:28
  • $\begingroup$ 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? $\endgroup$ – Flo Pfender Jun 8 '12 at 8:04
  • 4
    $\begingroup$ Where is the example of Chudnovsky & Seymour? $\endgroup$ – Gerry Myerson Aug 12 '14 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.