BIB-VERSION:: CS-TR-v2.0
          ID:: STAN//CS-TR-69-126
       ENTRY:: November 27, 1995
ORGANIZATION:: Stanford University, Department of Computer Science
       TITLE:: Complementary spanning trees
        TYPE:: Technical Report
      AUTHOR:: Dantzig, George B.
        DATE:: March 1969
       PAGES:: 12
    ABSTRACT:: Given a network G whose arcs partition into
               non-overlapping 'clubs' (sets) $R_i$, D. Ray Fulkerson
               has considered the problem of constructing a spanning
               tree such that no two of its arcs belong to (represent)
               the same club and has stated necessary and sufficient
               conditions for such trees to exist. When each club
               $R_i$ consists of exactly two arcs, we shall refer to
               each of the arc pair as the 'complement' of the other,
               and the representative tree as a complementary tree.
               Our objective is to prove the following theorem: If
               there exists one complementary tree, there exists at
               least two.
       NOTES:: [Adminitrivia V1/Prg/19951127]
         END:: STAN//CS-TR-69-126