Tied Weights And Multiple Minimum Spanning Trees

When a Tie Matters

When several edges have the same weight, an algorithm for finding a minimum spanning tree may have choices. Sometimes different choices lead to distinct minimum spanning trees of the same total weight. Sometimes the tied edges are irrelevant: every minimum spanning tree uses the same edges, even though some weights repeat. The key is not merely whether weights tie, or whether a cycle has a tied maximum, but whether an equal-weight exchange is possible within a minimum spanning tree.

Throughout, let \(G=(V,E)\) be a finite, connected, simple graph with edge-weight function \(w:E\to\mathbb{R}\). A spanning tree is a connected, acyclic subgraph containing every vertex of \(G\). A minimum spanning tree (MST) is a spanning tree whose total weight, the sum of its edge weights, is least among all spanning trees of \(G\). We assume \(G\) is connected so that a spanning tree exists. If \(G\) has one vertex and no edges, its empty edge set is its unique spanning tree and MST.

For a tree \(T\) and an edge \(e=uv\) not in \(T\), there is a unique \(u\)-\(v\) path in \(T\). Adding \(e\) to \(T\) creates a cycle consisting of that path and \(e\); this is the fundamental cycle of \(e\) with respect to \(T\). We will use this cycle to test whether a tie can produce a different MST.

Proof. First note that for any \(e\notin E(T)\), every edge \(f\) on its \(T\)-path satisfies \(w(f)\leq w(e)\). If instead \(w(f)>w(e)\), adding \(e\) and deleting \(f\) would give a spanning tree of smaller total weight than \(T\), contradicting that \(T\) is an MST.

If the strict condition fails for some non-tree edge \(e\), the inequality just proved means that some edge \(f\) on its \(T\)-path has \(w(f)=w(e)\). Adding \(e\) to \(T\) creates its fundamental cycle, which contains \(f\). Deleting \(f\) breaks that cycle and leaves a spanning tree: the added edge reconnects the two components formed by deleting \(f\) from \(T\). The new tree has the same total weight as \(T\), since it replaces \(f\) by \(e\) of equal weight. It is distinct from \(T\), so \(T\) is not unique.

Conversely, suppose the strict condition holds, but that \(T'\) is a different MST. Choose \(e\in E(T')\setminus E(T)\). Deleting \(e\) from \(T'\) separates \(T'\) into two components. The \(T\)-path between the endpoints of \(e\) crosses between those components, so it contains an edge \(f\) whose endpoints are in different components. This \(f\) cannot be in \(T'\), because the only edge deleted from \(T'\) was \(e\), and every other edge of \(T'\) stays within one of the two components. Thus \(f\in E(T)\setminus E(T')\). By the strict condition, \(w(f)<w(e)\). But \(T'-e+f\) is a spanning tree with smaller total weight than \(T'\): \(f\) reconnects the two components, and it is lighter than the removed edge \(e\). That contradicts the minimality of \(T'\). Hence no such distinct \(T'\) exists, and \(T\) is unique. \(\square\)

This criterion makes the role of a tie precise. If a non-tree edge ties in weight with an edge on its path in \(T\), exchanging them gives a second MST. If every non-tree edge is strictly heavier than every edge on its \(T\)-path, no such equal-weight exchange is possible, and the criterion proves that \(T\) is unique.

Worked Examples

How Cycle Ties Relate to the Test

The examples separate two claims that are easy to confuse. In the first example, two maximum-weight edges on a cycle can be exchanged while retaining a minimum total weight. In the third, two maximum-weight edges on a cycle exist, but both are heavier than the edges on their paths in the unique MST, so neither can replace a tree edge without increasing the total weight. The relevant question is not just whether a cycle has a tied maximum; it is whether a non-tree edge ties an edge on its path in an MST.

There is a useful special case. If the whole graph is a cycle, every spanning tree is obtained by deleting one edge. If the maximum edge weight on that cycle is attained at least twice, deleting either of two maximum-weight edges leaves a spanning tree of the same minimum total weight. If instead the maximum occurs only once, deleting that unique heaviest edge gives the unique minimum-weight spanning tree of the cycle. In graphs with additional edges, the situation can differ, as the third example demonstrates.

A common mistake is to apply the special case for a graph that is itself a cycle to any cycle inside a larger graph.

For instance, in the third example, the cycle weights are \(2,5,5,1\), so its tied maximum is indeed \(5\). But the two non-tree edges each have weight \(5\), while the largest edge on either corresponding tree path has weight \(3\). Substituting gives \(5>3\) in both cases, so the uniqueness test passes. The correction is to examine the fundamental paths, not just the weights around an arbitrary cycle.

Why the Exchange Test Is Useful

The test is useful when a minimum spanning tree has already been found and the weights contain ties. It does not require listing every spanning tree. For each edge outside the chosen tree, find the tree path between its endpoints and compare weights. A tie with any edge on that path gives a second MST by swapping those edges. If all comparisons are strict, the proof of the theorem rules out every other MST.

This also explains why two runs of an algorithm can return different trees when ties occur, without either answer being wrong: if a valid equal-weight exchange is available, both trees have the same minimum total weight. But a different tie-breaking order does not necessarily change the result. Tied edges may be forced out of a minimum tree, or may be too heavy to replace any tree edge, as the examples show. Weight repetition signals a choice to investigate; the path comparisons determine whether it affects uniqueness.