The Algebra of Sets of Trees, k-Trees, and Other Configurations

In linear graphs a commutative ring (Wang algebra) yields relations between sets of partial graphs such as trees, -trees, cut sets, circuits, and paths. This algebra is defined, explored, and applied, resulting in a unified approach by which theorems long connected with Wang algebra are rederived and new theorems are obtained. Some scattered relations, previously found by the method of "derivatives," appear as natural and special results. Special stress is put on the generation of sets of partial graphs in graphs compounded by interconnecting disjoint graphs, or by methods of cutting up the given graph. Many new theorems are derived which simplify computations by splitting a given problem into several of smaller dimension.