Proving triangle inequality using complete-linkage between clusters and arbitrary dissimilarity measure Assuming a dissimilarity measure d satisfies the usual properties, I need to prove that complete linkage ( i.e. d(A,B)=maxx∈A,y∈B{d(x,y)} ) either satisfies or does not satisfy the triangle inequality property when also considering a further cluster C={z1,...,zm}:
d(A,C)≤d(a,b)+d(B,C)
We have been told that the statement is true. Knowing this it seems that we will somehow here end up proving that the sum of the maximums is greater than the maximum of the sums but I really don't know how to begin putting this together (or if this is definitely correct).

Let $a, c$ be the points in $A$ and $C$ with the greatest distance (i.e. $d(a,c) = d(A,C)$). Let $b$ be any point in $B$.
Then $d(a,c) \leq d(a,b) + d(b,c)$ because $d$ is metric.
But we know that $d(a,b) \leq d(A,B)$ because the latter is the maximum of all such distances. The same applies to $d(b,c)$.
Thus, $d(A,C) = d(a,c) \leq d(a,b) + d(b,c) \leq d(A,B) + d(B,C)$ which we wanted to show.
