Next: Proof of Theorem 1 Up: Appendix A. Proofs Previous: Appendix A. Proofs

## 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 d0 = 0. For any node N, if i=N.label, we define d(N) = di. 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 x2 ... xp in instantiate1. Else, let N=N1, N2 ... Nq=M be the path from N to M through T. By the definition of a cluster tree, it follows that Ni.label < N.label, for i > 1 and therefore d(Ni) << d(N). Thus od(G[M],G[N]) <<= (by the o.m.-triangle inequality) maxi=1 ... q-1(od( G[Ni+1],G[Ni])) <<= maxi=1 ... q-1(d(Ni)) (since Ni+1 is the child of Ni) <<= d(N).

ii.
Let N be a node in T; let C1 and C2 be two distinct children of N; and let M1 and M2 be descendants of C1 and C2 respectively. Then od( G[M1], G[M2]) = d(N). Proof: By the construction of x2 ... xp in instantiate1(N), od( G[C1],G[C2]) = d(N). By part (i.), od( G[M1],G[C1]) <<= d(C1) << d(N) and likewise od( G[M2],G[C2]) << d(N). Hence, by axiom A.6, od( G[M1], G[M2]) = 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.

Next: Proof of Theorem 1 Up: Appendix A. Proofs Previous: Appendix A. Proofs