# Can the MST's "cut property" be derived from the "cycle property" and vice versa?

The cut and cycle properties of the minimum spanning tree are well-known. It is easy to use similar arguments to prove them. But I wonder if one property be derived from the other.

Cut property: Suppose edges X are part of an MST of G=(V, E). Pick any subset of nodes S for which X does not cross between S and V-S, and let e be the lightest edge across this partition. Then X + {e} is part of some MST.

Cycle property: Pick any cycle in the graph, and let e be the heaviest edge in that cycle. Then, there is an MST that does not contain e.

From Dashupta, Papadimitrionu, and Vazirani's Algorithms

• I am not sure what you are asking. Since those properties are both true, yeah, from a logic point of view, they imply each other (since true implies true). Feb 28 at 22:43
• I meant to ask if one property can be derived from the other. Feb 28 at 23:06

The technical answer is that they imply each other. Since they are both true statements either implication evaluates to $$T \to T$$ which is a true statement. However, I know that you are really asking if you can prove MSTs have the cycle property only using the fact that they have cut property. The answer is no.
We define a 1-tree to be a connected graph with exactly one cycle. Informally, they are trees plus an edge. Then minimum spanning 1-trees (MS1T) of a graph $$G$$ satisfy the cut property, but not necessarily the cycle property. Thus the cut property is not enough to prove the cycle property.