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