Perfect pairs of trees in graphs

Abstract

We introduce the concept of perfect pairs of trees of a graph as a natural generalization of so‐called maximally distant pairs of trees. Several propositions and remarks are presented to display the properties of this new notion. Lemma 1, which plays a central role, gives five equivalent statements characterizing the relation ‘to be maximally distant from’ between pairs of trees. Symmetrization of this relation leads to our concept of a perfect pair of trees, the properties of which are given in Theorem 1. Remark 4 shows how naturally our new concept arises. Additionally, certain examples are provided to illustrate perfect pair structures in a graph. Copyright © 1992 John Wiley & Sons, Ltd.