# Necessary and sufficient condition for unique minimum spanning tree

This is an exercise problem (Ex.3) from the excellent lecture note by Jeff Erickson Lecture 20: Minimum Spanning Trees [Fa’13] .

Prove that an edge-weighted graph $G$ has a unique minimum spanning tree if and only if the following conditions hold

• For any partition of the vertices of $G$ into two subsets, the minimum-weight edge with one endpoint in each subset is unique.

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

Consider the "$\Rightarrow$" direction and the following graph $G$.

$G$ has a unique MST. However, for the partition $\{A\}$ and $\{B,C\}$, the minimum-weight crossing edge is not unique.

Did I misunderstand some points? Or if there are flaws in the theorem, how can we fix it?

• Yes, this seems to be a mistake. Try to figure out what version of the exercise is correct. For example, it seems that the second condition is indeed necessary. – Yuval Filmus Dec 8 '14 at 19:54
• Unless I misunderstand, the second condition is not necessary either. Consider the graph {(A,B,1), (A,C,1), (A,D,1), (B,D,10), (D,C,10)}. It also has a minimum spanning tree composed of edges connected to A. But there is a cycle with 2 maximum weight edges (and the first condition is not met either). CC @YuvalFilmus – babou Jun 1 '15 at 11:04
• @jeffe, what do you think? ;) – Luke Mathieson Jun 1 '15 at 13:04
• I think the second should be in "in any chordless cycle" (so a minimal cycle in the sense that it doesn't include smaller ones as induced subgraphs). The first condition seems significantly wrong. For example take $G$ to be any tree where all edge weights are $1$, then $G$ has a unique MST (itself), but any partition with more than one edge crossing it has several minimum weight edges. – Luke Mathieson Jun 1 '15 at 13:15
• Oops! Yes, this is a bug. (Note to self: Change every instance of "Prove" to "Prove or disprove".) – JeffE Oct 29 '15 at 23:32