Single Linkage, Minimum Spanning Trees, and Connected Components

Why a Tree Can Represent Single Linkage

Single linkage joins two clusters when their closest pair of members is close enough. At a fixed dissimilarity threshold, this means that objects can belong to the same cluster through a chain of short links; the first and last objects in that chain need not be close to each other. A minimum spanning tree preserves exactly the connectivity information needed to identify those chains, even though it retains only a small subset of all pairwise links.

This connection is useful when interpreting single-linkage results and when a problem supplies a weighted graph rather than a full distance matrix. The key is to threshold the tree’s edges and find its connected components—not to treat each retained edge as a separate cluster. The result is aligned with the SOA Exam SRM (Statistics for Risk Modeling) syllabus.

Definition: Let \(V\) be a finite set of objects and let \(\Delta(i,j)\) be the symmetric dissimilarity between objects \(i\) and \(j\), with finite nonnegative values. Form the complete weighted graph whose vertices are the objects and whose edge \((i,j)\) has weight \(\Delta(i,j)\). For a threshold \(t\), the threshold graph contains exactly the edges with weight at most \(t\). Its connected components are the maximal groups of vertices joined by paths of retained edges. A minimum spanning tree (MST) is a spanning tree of minimum total edge weight.

A tree on \(n\) vertices has \(n-1\) edges. Thus an MST compresses the complete graph’s \(\binom{n}{2}\) pairwise dissimilarities to \(n-1\) selected edges. It is still important to keep the threshold rule explicit: throughout this tutorial an edge is retained when its weight is less than or equal to \(t\).

Single-Linkage Clusters as Graph Components

For two nonempty clusters \(C_1\) and \(C_2\), their single-linkage dissimilarity is the smallest pairwise dissimilarity between their members:

D_{\mathrm{single}}(C_1,C_2) =\min_{i\in C_1,\ j\in C_2}\Delta(i,j).

At threshold \(t\), single linkage joins clusters whenever their minimum cross-cluster dissimilarity is at most \(t\). Equivalently, imagine placing an edge between every pair of objects whose dissimilarity is at most \(t\). Objects joined by a path of such edges end up in the same cluster: each edge along the path provides a single-link connection, even if the endpoints themselves have dissimilarity greater than \(t\).

Theorem: For any finite set of objects with finite symmetric dissimilarities, the single-linkage clusters at threshold \(t\) are exactly the connected components of the complete threshold graph containing edges of weight at most \(t\). They are also exactly the connected components formed by retaining only the MST edges of weight at most \(t\).

Why Thresholding an MST Gives the Same Clusters

The first equality follows from the single-linkage rule: two objects become connected precisely when there is a chain of pairwise dissimilarities no greater than \(t\). The less immediate part is that one MST is enough to preserve this connectivity at every threshold. The argument uses the fact that an MST cannot contain an edge that can be replaced by a strictly lighter edge without breaking the spanning-tree property.

Threshold the complete graph.
Keep every edge of weight at most \(t\). Consider any two vertices connected in this graph, and choose a path between them using only retained edges.

Compare with the MST path.
The MST has a unique path between the same two vertices. Suppose that path contains an edge \(e\) with weight greater than \(t\). Removing \(e\) separates the tree into two parts.

Use a lighter crossing edge.
The complete-graph path from Step 1 must cross between the two parts. A crossing edge \(f\) on that path has weight at most \(t\), so its weight is strictly less than the weight of \(e\).

Reach a contradiction.
Replacing \(e\) by \(f\) reconnects the tree and gives a spanning tree of smaller total weight. That contradicts the definition of an MST. Therefore every edge on the MST path has weight at most \(t\).

This proves that vertices connected in the complete threshold graph are connected in the thresholded MST. The reverse direction is immediate: every MST edge is an edge of the complete graph, so any path using MST edges of weight at most \(t\) is also a path in the complete threshold graph. The two graphs therefore have the same connected components.

The same reasoning gives a useful bottleneck interpretation. For vertices \(u\) and \(v\), the largest edge weight on their MST path is the smallest possible maximum edge weight over all paths connecting them:

\max_{e\in \operatorname{path}_T(u,v)} w(e) = \min_{P:\,u\leadsto v}\ \max_{e\in P} w(e).

In words, the right side asks for a path from \(u\) to \(v\) whose most expensive edge is as small as possible. The MST path achieves that bottleneck. Consequently, the two vertices first belong to the same single-linkage cluster at the threshold given by their MST-path bottleneck.

Worked Examples on Weighted Graphs

Worked Example: Finding Clusters at Two Thresholds

A hypothetical grouping exercise has five objects \(A,B,C,D,E\). The complete graph’s edge weights are listed below. Find an MST, then determine the single-linkage clusters at thresholds \(t=2\) and \(t=3\). State the method and check the result against the single-linkage rule.

Edge	Weight	Edge	Weight
AB	1	AC	4
BC	2	AD	7
CD	3	AE	8
DE	2	BD	6
CE	5	BE	7

Method: Kruskal’s algorithm. Sort edges from smallest to largest and add an edge when it connects two components that are not already connected. The sorted weights begin \(1,2,2,3,4,\ldots\). Add \(AB\) (weight 1), \(BC\) (weight 2), and \(DE\) (weight 2). These form components \(\{A,B,C\}\) and \(\{D,E\}\). The next edge \(CD\), of weight 3, connects those components and completes the tree. The MST has total weight \(1+2+2+3=8\).

At \(t=2\), the retained MST edges are \(AB,BC,DE\). They give components \(\{A,B,C\}\) and \(\{D,E\}\). At \(t=3\), \(CD\) is retained as well, so all five objects are connected: \(\{A,B,C,D,E\}\).

Check. In the full graph, the edges of weight at most 2 are also \(AB,BC,DE\); the edge \(CD\) first becomes available at 3. Thus the full threshold graph gives the same two partitions. A common mistake is to count only the tree edges as separate clusters. Clusters are connected components, so \(A,B,C\) form one cluster at \(t=2\), not three.

Worked Example: Finding the Connection Threshold for Two Objects

Four objects \(P,Q,R,S\) have pairwise dissimilarities \(PQ=2\), \(QR=4\), \(RS=3\), \(PR=7\), \(PS=9\), and \(QS=6\). Find an MST, the clusters at threshold 3, and the smallest threshold at which \(P\) and \(S\) belong to the same single-linkage cluster. Use the bottleneck-path method and check the answer using the original graph.

Step 1: Build the MST. In increasing order, the edge weights are \(PQ=2\), \(RS=3\), \(QR=4\), \(QS=6\), \(PR=7\), and \(PS=9\). Kruskal’s algorithm first selects \(PQ\) and \(RS\), which create two components. It then selects \(QR\), which joins them. The MST is \(\{PQ,RS,QR\}\), with total weight \(2+3+4=9\).

Step 2: Threshold at 3. Retain \(PQ\) and \(RS\), but not \(QR\). The components are \(\{P,Q\}\) and \(\{R,S\}\).

Step 3: Find the \(P\)-to-\(S\) bottleneck. The MST path is \(P-Q-R-S\), with edge weights \(2,4,3\). Its largest edge has weight 4, so the bottleneck is 4. At threshold 4, all three path edges are retained and \(P,S\) are connected.

Check. At any threshold below 4, \(Q\) and \(R\) are not connected by any available crossing edge: their direct edge has weight 4, while the alternatives \(QS=6\), \(PR=7\), and \(PS=9\) are heavier. Thus no path can connect \(P\) to \(S\) below 4. The smallest connecting threshold is exactly 4. The common error of using the direct dissimilarity \(PS=9\) would miss the shorter chain through \(Q\) and \(R\).

Worked Example: Tied Weights and Different MSTs

Four objects \(W,X,Y,Z\) have dissimilarities \(WX=1\), \(XY=2\), \(XZ=2\), \(YZ=2\), \(WY=5\), and \(WZ=6\). Find two possible MSTs and compare their threshold components at \(t=1\) and \(t=2\). Explain why the tie does not change the single-linkage partition.

Method: apply Kruskal’s algorithm while allowing either tied edge. The first edge selected is \(WX\), with weight 1. The three edges \(XY,XZ,YZ\) all have weight 2. Selecting \(XY\) and \(YZ\) completes one MST, \(\{WX,XY,YZ\}\), with total weight \(1+2+2=5\). Alternatively, selecting \(XZ\) and \(YZ\) completes another MST, \(\{WX,XZ,YZ\}\), also with total weight 5.

At \(t=1\), either tree retains only \(WX\), so the components are \(\{W,X\}\), \(\{Y\}\), and \(\{Z\}\). At \(t=2\), both trees connect all four objects. In the first tree, \(Y\) joins through \(XY\) and \(Z\) through \(YZ\); in the second, \(Z\) joins through \(XZ\) and \(Y\) through \(YZ\). The particular tree edges differ, but the components agree at both thresholds.

Check. The full threshold graph at \(t=2\) contains all three weight-2 edges among \(X,Y,Z\), so those vertices are connected, and \(WX\) attaches \(W\). Ties can produce different MSTs and different merge choices, but not different threshold partitions. Choosing a tied edge that closes a cycle, such as all three weight-2 edges, would not be an MST because a tree cannot contain that cycle.

Threshold Conventions and Common Traps

The MST result depends on the graph’s connectivity, not on a requirement that dissimilarities satisfy every metric axiom. In particular, the triangle inequality is not needed for the proof. What is needed here is a finite set of objects and finite symmetric edge weights so that the complete weighted graph is connected and an MST exists. If a problem instead gives a sparse graph, the same component result applies to that graph and one of its MSTs when the graph is connected; edges that are absent are not available paths.

Keep these distinctions clear when reading a question:

A threshold is inclusive here. An edge of weight exactly \(t\) is retained, because the rule is weight at most \(t\).
Clusters are components, not edges. A chain of retained edges can connect objects whose direct dissimilarity exceeds \(t\).
The tree is not the entire distance graph. It preserves threshold connectivity, not every pairwise dissimilarity or every edge.
Tied MSTs are allowed. Different choices among tied edges can give different trees while preserving the same components at every threshold.

For example, in the first worked example, using the incorrect strict rule “retain edges with weight less than 2” keeps only \(AB\). That would produce \(\{A,B\},\{C\},\{D\},\{E\}\). With the correct rule “retain edges with weight at most 2,” the weight-2 edges \(BC\) and \(DE\) are also included, giving \(\{A,B,C\}\) and \(\{D,E\}\). Always check whether the problem states \(<t\) or \(\leq t\); the equality case changes the answer.

Key takeaway: To obtain single-linkage clusters at threshold \(t\), keep MST edges of weight at most \(t\) and report the connected components. The largest edge on the MST path between two objects is the smallest threshold at which they become connected.

Check Your Understanding

For each problem, identify the relevant threshold graph or MST path before stating the result.

A four-object complete graph has \(AB=1\), \(AC=5\), \(AD=8\), \(BC=3\), \(BD=6\), and \(CD=2\). Find an MST and the single-linkage clusters at \(t=2\) and \(t=3\). (Answer: An MST is \(AB,CD,BC\); at \(t=2\) the clusters are \(\{A,B\}\) and \(\{C,D\}\), and at \(t=3\) all four objects form one cluster.)
A graph on \(R,S,T,U,V\) has edge weights \(RS=1\), \(ST=4\), \(TU=2\), \(UV=3\), \(RU=8\), \(RT=6\), \(SU=5\), \(SV=7\), \(RV=9\), and \(TV=6\). Give an MST, the components at \(t=3\), and the first threshold connecting \(R\) to \(V\). (Answer: An MST is \(RS,TU,UV,ST\); at \(t=3\) the components are \(\{R,S\}\) and \(\{T,U,V\}\); \(R\) and \(V\) first connect at threshold 4.)
A complete graph has \(AB=2\), \(BC=2\), \(AC=2\), \(CD=5\), \(BD=7\), and \(AD=8\). At \(t=2\), how many clusters are there, and what are they? Does choosing a different MST change the answer? (Answer: There are two clusters, \(\{A,B,C\}\) and \(\{D\}\); no, a different MST gives the same threshold components.)
On an MST, the unique path from \(M\) to \(N\) has edge weights \(1,4,3,6\). What is the smallest threshold at which \(M\) and \(N\) are in the same single-linkage cluster, and why is the sum of the path weights not the answer? (Answer: The threshold is 6, the largest edge on the path; the path’s total length does not determine connectivity.)
At threshold \(t=4\), a threshold graph contains edges \(JK=4\), \(KL=3\), and \(MN=2\), with no other edges of weight at most 4. State its components and the effect of mistakenly using a strict cutoff. (Answer: With the inclusive cutoff the components are \(\{J,K,L\}\) and \(\{M,N\}\); a strict cutoff excludes \(JK\) and instead gives \(\{J\},\{K,L\},\{M,N\}\).)

What You'll Learn