I'm conjecturing that with Complete-linkage clustering two elements from the same cluster will always be closer to each other some other element from another cluster.

In more formal terms:

Let $C$ be a clustering. $\not\exists z \in C_j$ s.t. $\bigtriangleup(x, z) < \bigtriangleup(x, y)$ where $x,y \in C_i$, $C_i \neq C_j$ and $C_i, C_j \in C$.

I haven't been able to prove the conjecture yet, thus I'm wondering whether I'm right or wrong. If this is indeed the case, I would much appreciate a sketch a proof. I'm pretty sure I can work my way from there.

On a side note (not that I think it makes a difference), I'll be applying the clustering algorithm on a one-dimensinal dataset.

• Did you perhaps manage to prove your conjecture meanwhile? – VividD May 11 '17 at 12:09

Complete-linkage clustering tends to find compact clusters with equal diameters. It is define the inter-group distances as the largest distance of objects between two clusters. Beside, it is may produce clusters that has the same number of objects and the distance between objects is contiguous.

So, I can say that your conjecture is correct. I cannot wait for any experts to explain this in detail.

I may have missed something in the definition in Wikipedia, but wouldn't the set {1,2,4,5,7,8} with $\Delta(x,y) = |x-y|$ be a counterexample? After the 4th step there are two clusters, {{1,2}, {4,5}}, {7,8} and x=5, y=1, z=7 seems to violate your claim.