8
$\begingroup$

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$.

mst

$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?

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Dec 8 '14 at 19:54
  • 2
    $\begingroup$ 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 $\endgroup$ – babou Jun 1 '15 at 11:04
  • $\begingroup$ @jeffe, what do you think? ;) $\endgroup$ – Luke Mathieson Jun 1 '15 at 13:04
  • $\begingroup$ 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. $\endgroup$ – Luke Mathieson Jun 1 '15 at 13:15
  • 1
    $\begingroup$ Oops! Yes, this is a bug. (Note to self: Change every instance of "Prove" to "Prove or disprove".) $\endgroup$ – JeffE Oct 29 '15 at 23:32
0
$\begingroup$

Answer my own question by simply copying the comment made by @JeffE, the author of the lecture note:

Oops! Yes, this is a bug. (Note to self: Change every instance of "Prove" to "Prove or disprove".) – JeffE

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.