# Accession Number:

## AD0702898

# Title:

## COMPLEMENTARY SPANNING TREES

# Descriptive Note:

## Technical rept.

# Corporate Author:

## STANFORD UNIV CA DEPT OF COMPUTER SCIENCE

# Personal Author(s):

# Report Date:

## 1969-03-01

# Pagination or Media Count:

## 12.0

# Abstract:

Given a network G whose arcs partition into non-overlapping clubs sets R sub 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 sub 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.

# Descriptors:

# Subject Categories:

- Theoretical Mathematics
- Operations Research