Hamilton Circuits in Tree Graphs

Two operations for augmenting networks (linear graphs) are defined: edge insertion and vertex insertion. These operations are sufficient to allow the construction of arbitrary nonseparable networks, starting with a simple circuit. The tree graph of a network is defined as a linear graph in which each vertex corresponds to a tree of the network, and each edge corresponds to an elementary tree transformation between trees of the network. A property of tree graphs, referred to as "Property H," is defined: if and are two trees of a network, and if and are related by an elementary tree transformation, then there exists a Hamilton Circuit through the tree graph such that and are adjacent in the circuit. It is shown that any tree graph containing more than two vertices has Property H.