# Is this "cycle" condition sufficient for unique minimum spanning tree?

Given a connected, undirected, weighted graph $G$, the condition

The maximum-weight edge in any cycle of $G$ is unique.

is not necessary for $G$ to have a unique minimum spanning tree (MST).

However, is this condition sufficient for $G$ to have a unique MST?

• No. Consider {AB -> 3, BC -> 4, CD -> 3, DA -> 4}. ABC and ADC (and BCD and DAB) are minimal spanning trees. AB = CD and AD = BC. May 29, 2017 at 14:36
• @Thumbnail The graph you use does not satisfy the condition above. You are showing that the condition is not necessary for $G$ to have the unique MST. However, I am wondering whether it is sufficient. May 30, 2017 at 4:22

Answer My Own Question by attempting to prove that the condition above is sufficient for a graph $G$ to have a unique MST. I am asking for reviews. Thanks in advance.

First, for each cycle, the unique heaviest edge in it must be not in any MST. Consider the remaining graph $G'$, obtained by keeping removing the unique heaviest edges in cycles from $G$. All MSTs are part of $G'$. If we can show that $G'$ is a spanning tree, then $G'$ is the unique MST of $G$.

$G'$ is connected because each edge removed belongs to a cycle when it was removed.
$G'$ is acyclic because we are keeping breaking cycles. Thus, $G'$ is a spanning tree.

• I'd say your proof is valid. If you iteratively remove the heaviest edge from each cycle and the resulting graph is a spanning tree then it has to be minimal. The elimination ordering doesn't matter because a cycle won't break until an edge is removed, hence why the resulting graph is unique. May 30, 2017 at 8:19