THE NUMBER OF ISOMORPHISM CLASSES OF SPANNING TREES OF A GRAPH

I n [ l] B. L. H a r t n e l l conjectures that the spanning trees of a graph containing n vertex-disjoint circuits can be partitioned into at least n + 1 isomorphism classes. We shall prove this conjecture. All graphs considered here are finite undirected graphs without loops and multiple edges. First we shall define some concepts which will be used in the sequel. In [2] some concepts concerning trees are defined. For a vertex a of a tree T the mean vertex deviation is defined as mM)=Wn\Jj^xh where V(T) denotes the vertex set of T (this symbol will be used also for other graphs) and d(a, x) denotes the distance between the vertices a and x in T. A vertex of T with the minimal vertex deviation is called a median of T and its mean vertex deviation is called the mean vertex deviation of T. In [3] it is proved that each tree has either exactly one median, or exactly two medians which are joined by an edge. (The concept of a median is defined in [2] not only for trees, but her