THE EXISTENCE AND GENERATION OF A HAMILTON CIRCUIT IN A TREE GRAPH.

The existence of a Hamilton circuit in a tree graph was first proved by R. L. Cummins in his Ph. D. thesis at the University of Illinois. However, the proof involves complicated procedures, and it is hard to apply it to the generation of all the trees in a given graph. The new proof, which is straightforward and concise, is given in this paper. This proof is constructive and applicable to the generation of all the trees in a given graph. A general procedure for obtaining a Hamilton circuit in a tree graph is shown. By applying this procedure, all the trees in a graph with 5 vertices and 8 edges are generated in an example. The procedure is of recursive nature and hence suitable for computation by a digital computer. Author