0
$\begingroup$

http://homepages.math.uic.edu/~leon/cs-mcs401-s08/handouts/mst.pdf enter image description here

I have some trouble understanding the proof above.

I understand that we assuming two MSTs, T and T', and an edge e that is the cheapest edge of G that located in T. Then the weight of this edge is larger than any weight on T', given that T' contains (x,y), by definition of MST.

My question is why do we assume that T' passes through (x,y)? Wouldn't it natural to assume that T' is completely disjoint from T?

$\endgroup$
1
  • 2
    $\begingroup$ Don't use images as main content of your post. This makes your question impossible to search and inaccessible to the visually impaired; we don't like that. Please transcribe text and mathematics (note that you can use LaTeX) and don't forget to give proper attribution to your sources! $\endgroup$
    – Raphael
    Dec 16 '14 at 22:30
0
$\begingroup$

The edge $e$ is not necessarily the cheapest edge of $G$ that is in $T$. Rather, it is the cheapest edge in the symmetric difference $T \triangle T'$. It could belong to either $T$ or $T'$ (but not both!), but since both cases are the same, we assume that it belongs to $T$ without loss of generality.

We don't need to separately consider the case that $T$ is disjoint from $T'$ and the case that they share some edges. All we need to know is that they are different and so their symmetric difference is not empty.

$\endgroup$
2
  • $\begingroup$ Thanks, do you know of a better proof that exists because this one requires too much mind bending $\endgroup$
    – Fraïssé
    Dec 16 '14 at 21:47
  • 2
    $\begingroup$ This is the same as the proof I know. I wouldn't rate it as "mind bending", especially given proofs you will see in the future. It is better to be able to comprehend this proof now, since otherwise you will have trouble in the future with more complicated proofs. $\endgroup$ Dec 16 '14 at 21:48

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.