Proof of lemma 2

**Lemma 2:** If *T* is a cluster tree and *O* is an om-space, then
instantiate(*T*,*O*) returns an instantiation of *T*.

**Proof:** Let *d*_{0} = 0.
For any node *N*, if *i*=*N*.label, we define
*d*(*N*) = *d*_{i}. The proof then proceeds in the following
steps:

- i.
- For any nodes
*M*,*N*, if*M*is a descendant of*N in T*then od(*G[M]*,*G[N]*) <<=*d*(*N*).**Proof:**If*M*is a child of*N*, then this is immediate from the construction of*x*_{2}...*x*_{p}in instantiate1. Else, let*N*=*N*_{1},*N*_{2}...*N*_{q}=*M*be the path from*N*to*M*through*T*. By the definition of a cluster tree, it follows that*N*_{i}.label <*N*.label, for*i*> 1 and therefore*d*(*N*_{i}) <<*d*(*N*). Thus od(*G[M]*,*G[N]*) <<= (by the o.m.-triangle inequality)*max*_{i=1 ... q-1}(od(*G[N*_{i+1}*]*,*G[N*_{i}*]*)) <<=*max*_{i=1 ... q-1}(*d*(*N*_{i})) (since*N*_{i+1}is the child of*N*_{i}) <<=*d*(*N*). - ii.
- Let
*N*be a node in*T*; let*C*_{1}and*C*_{2}be two distinct children of*N*; and let*M*_{1}and*M*_{2}be descendants of*C*_{1}and*C*_{2}respectively. Then od(*G[M*_{1}*]*,*G[M*_{2}*]*) =*d*(*N*).**Proof:**By the construction of*x*_{2}...*x*_{p}in instantiate1(*N*), od(*G[C*_{1}*]*,*G[C*_{2}*]*) =*d*(*N*). By part (i.), od(*G[M*_{1}*]*,*G[C*_{1}*]*) <<=*d*(*C*_{1}) <<*d*(*N*) and likewise od(*G[M*_{2}*]*,*G[C*_{2}*]*) <<*d*(*N*). Hence, by axiom A.6, od(*G[M*_{1}*]*,*G[M*_{2}*]*) =*d*(*N*). - iii.
- Let
*a*and*b*be any two leaves in*T*, and let*N*be the least common ancestor in*T*of*a*and*b*. Then od(*G[a]*,*G[b]*) =*d*(*N*).**Proof:**Immediate from (ii). - iv.
- For any node
*N*, odiam(*Z*(*N*)) =*d*(*N*).**Proof:**From (iii), any two leaves descending from different children of*N*are at a distance of order*d*(*N*), and no two leaves of*N*are at a distance of order greater than*d*(*N*). - v.
- For any node
*N*,*Z*(*N*) is a cluster of*Z*(*T*).**Proof:**Let*a*and*b*be leaves of*N*, and let*c*be a leaf of*T*-*N*. Let*I*be the common ancestor of*a*and*b*in*T*and let*J*be the common ancestor of*a*and*c*. Then*I*is either*N*or a descendant of*N*and*J*is a proper ancestor of*N*. Therefore by part (i),*d*(*I*) <<*d*(*J*). But by (iii), od(*Z*(*a*),*Z*(*b*)) =*d*(*I*) <<*d*(*J*) = od(*Z*(*a*),*Z*(*c*)). - vi.
- For any internal nodes
*N*,*M*if*M*.label <*N*.label then odiam(*Z*(*M*)) << odiam(*Z*(*N*)).**Proof:**Immediate from (iv) and the construction of*d*. - vii.
- If
*C*is a cluster of*Z*(*T*) then there is a node*N in T*such that*C*=*Z*(*N*).

**Proof:**Let*S*be the set of symbols corresponding to*C*and let*N*be the least common ancestor of all of*S*. Let*a*and*b*be two symbols in*S*that are in different subtrees of*S*. Then by (iii), od(*G[a], G[b]*) =*d(N}*. Let*x*be any symbol in*N*.symbols. Then by (iii) od(*G[a], G[x]*) <<=*d(N)*. Hence*G[x] in C*.