ON THE THEOREMS OF GENERATION OF TREES BY DECOMPOSITION WITHOUT DUPLICATIONS

A complementary partitive graph is a bipartite graph G(V , V; E) with disjoint vertex sets V , V, and an edge set E such that all edges are directed except only one edge, say j=[x, y], is undireeted, and the outgoing degrees are d+(x)=0, d+(y)=0 and d+(v)=1 for all vx, y. The following assertions can be easily proved: If G(v' , V; E) is a complementary partitive graph with undireeted edge j, then a pair of eomple mentary partitions P' (E) and P(E) with respect to j can be constructed by the edges incident with each vertex of V' and each vertex of V'' . Conversely, if Hk has a complementary partition with respect to j, then a complementary partitive graph can be constructed. by using the complementary partiive graph defined above. We can ease the proofs of theorems of complementary partitions established by W. K. chen (1969, 1976) and give a simple criterion to determine whether or not a complementary partition is essential as follows: Theorem A complementary partition is essential if and only if the corresponding complementary partitive graph is a connected graph.