The Dissimilarity Characteristic of Husimi Trees

The notion of dissimilarity characteristic for trees was introducted by Otter [4] in his theorem: any tree the number of nonsimilar vertices minus the number of nonsimilar lines (symmetry line excepted) is the number one. Using this theorem, Otter obtained a formula for the number of trees in terms of the known number of rooted trees. The definition of Husimi tree was given by Uhlenbeck [7] and Riddell [6] following a paper by Husimi [2] on the cluster integrals in the theory of condensation. Uhlenbeck interpreted Husimi's integral formulas in terms of the theory of graphs. A Husimi tree is a connected graph in which no line lies on more than one cycle. Uhlenbeck [7] proposed the problem of finding the number of Husimi trees, and showed how this result would be applicable to the theory of condensation. Harary and Uhlenbeck [1] obtained a functional equation for the number of rooted Husimi trees using the methods of Polya [5] as a partial solution of the above problem. In this paper a theorem on dissimilarity characteristic will be demonstrated for Husimi trees. The method of proof is essentially different from that used by Otter and gives more information by proving the theorem for multiply rooted trees. The use of this theorem in counting Husimi trees will be illustrated by a derivation of the formula for the number of purely triangular Husimi trees. In view of the pictorial appearance of triangular Husimi trees, we shall refer to them as cacti later. The counting of arbitrary Husimi trees is more difficult and is being investigated as a sequel to [1]. The ingenious methods of P6lya [5] will also he applied to the dissimilarity characteristic to yield an elegant proof of Otter's formula for the number of trees. One of the lemmas is of some independent interest, namely, the set of all central points of any connected graph lie on a subgraph which is a star. By a star' we mean a connected graph without articulation points.