Report Number: CS-TR-69-126
Institution: Stanford University, Department of Computer Science
Title: Complementary spanning trees
Author: Dantzig, George B.
Date: March 1969
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.
http://i.stanford.edu/pub/cstr/reports/cs/tr/69/126/CS-TR-69-126.pdf