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?

Improve this question
$\endgroup$
8
  • 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, 2014 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, 2015 at 11:04
  • $\begingroup$ @jeffe, what do you think? ;) $\endgroup$
    – Luke Mathieson
    Jun 1, 2015 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, 2015 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, 2015 at 23:32

1 Answer 1

Reset to default
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

Improve this answer
$\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.