The Cycle Property For Heavy Edges

Why a Heavy Edge on a Cycle Can Be Avoided

A spanning tree must connect every vertex without creating a cycle. When a graph contains a cycle, one of its edges can be removed without disconnecting the vertices. The weights matter: if one edge on that cycle is strictly heavier than all the others, it is never a sensible choice for a minimum spanning tree. The reason is an exchange: removing that edge from a spanning tree separates the tree into two parts, and another edge of the cycle reconnects those parts at lower weight.

Throughout, graphs are finite and simple, and each edge \(e\) has a real weight \(w(e)\). We consider a connected graph \(G=(V,E)\). A spanning tree of \(G\) is a subgraph that contains every vertex and is connected and acyclic. Its total weight is \(w(T)=\sum_{e\in E(T)}w(e)\). A minimum spanning tree (MST) is a spanning tree whose total weight is no greater than that of any other spanning tree of \(G\). A cycle is a closed sequence of edges through distinct vertices, apart from the repeated starting and ending vertex.

Because the graph is finite and connected, it has at least one spanning tree, and there are only finitely many spanning trees. Thus a minimum spanning tree exists. Edge weights need not be positive for this discussion.

The Cycle Property and Its Exchange Proof

Proof. Suppose, to obtain a contradiction, that a minimum spanning tree \(T\) contains \(e\). Removing an edge of a tree separates it into exactly two connected components: the unique path in \(T\) between the endpoints of \(e\) used \(e\), and without \(e\) those endpoints are disconnected; every vertex remains connected to one of the two endpoints by its former tree paths. Call the two components \(A\) and \(B\), with the endpoints of \(e\) in different components.

Traverse the cycle \(C\) from one endpoint of \(e\) to the other without using \(e\). This route starts in \(A\) and ends in \(B\), so at some step it uses an edge \(f\) with one endpoint in \(A\) and one in \(B\). This edge is not \(e\), and it lies on \(C\). Since \(e\) is uniquely heaviest on \(C\), \(w(f)<w(e)\).

Now form \(T'=(T-e)+f\). The graph \(T-e\) has two components, and \(f\) joins those components. Therefore \(T'\) is connected and contains every vertex. It is acyclic: any cycle using \(f\) would require a path between the components already present in \(T-e\), but no such path exists. Thus \(T'\) is a spanning tree. Its weight is \(w(T')=w(T)-w(e)+w(f)<w(T)\), contradicting the minimality of \(T\). Hence no MST contains \(e\). \(\square\)

The strict inequality is essential to this argument. If two or more edges tie for the greatest weight on a cycle, replacing one by another tied edge does not produce a strictly lighter tree. The cycle property therefore excludes a uniquely heaviest edge; it does not, by itself, exclude every edge tied for the maximum.

Minimum Spanning Trees of a Weighted Cycle

Proof. A spanning tree on \(n\) vertices has \(n-1\) edges. The cycle has \(n\) edges, so any spanning tree formed from its edges must omit exactly one edge. Conversely, deleting any one edge from the cycle leaves a path through all \(n\) vertices, which is connected and acyclic, and hence is a spanning tree. If the sum of all cycle-edge weights is \(S\), deleting an edge \(e\) gives a tree of weight \(S-w(e)\). This quantity is smallest exactly when \(w(e)\) is largest. If several edges tie for the largest weight, deleting any one of them gives a minimum; if the largest edge is unique, it is the unique edge omitted. \(\square\)

This proposition is specific to a graph that consists of a cycle and no other edges. In a larger graph, a cycle may have other routes and attachments, so subtracting the largest cycle-edge weight from the total weight of the whole graph is not a general way to compute an MST. The cycle property remains valid there as a local exclusion rule.

Using the Property Carefully

The cycle property is useful whenever a cycle in a weighted graph contains a uniquely heaviest edge. It lets us rule out that edge before constructing or comparing all spanning trees. It does not, on its own, determine which other edges must be selected, nor does it assert that every edge not ruled out belongs to an MST.

Common mistake: treating the cycle property as a rule to keep only one of the other cycle edges. In the triangle-with-attachment example, after \(bc\) is excluded, it is wrong to choose just \(ab\) or just \(ca\) to connect \(a,b,c\). If \(ab\) is chosen without \(ca\), then \(c\) is disconnected from \(a,b\); if \(ca\) is chosen without \(ab\), then \(b\) is disconnected from \(a,c\). Both \(ab\) and \(ca\) are needed, and with \(cd\) they form the spanning tree of weight \(2+3+1=6\).

Another important limitation is the strictness of the hypothesis. For a tied maximum on a cycle, the theorem’s premise fails. The tied-edge example shows why one cannot conclude that all maximum-weight edges are absent from every MST: either one can be retained if the other is omitted. The proposition for a graph that is itself a cycle describes this case precisely, but in a larger graph the tied edges must be considered in the context of the rest of the graph.

When applying the property, check three things: the edges really form a cycle; the edge being excluded is strictly heavier than every other edge on that cycle; and the graph is connected so that an MST is defined. The conclusion is only that the specified uniquely heaviest edge belongs to no MST.