Let be $G$ a weighted graph in which every edge has a different weight.

Suppose that $G$ has two spanning trees $A$ and $A'$. Let be $i$ the first index such that $e_i\ne e'_i$ and $i\ge 3$.

Suppose that $w(e_i)<w(e'_i)$ and consider that $A' \cup \{e_i\}$ has a unique cycle.

For each edge of this cycle then $w(e')<w(e_i)$ (else we would be able to create a tree $(A' \cup \{e_i\})\setminus\{e'\}$ of lower weight than $A'$, which contradicts the fact that $A'$ has minimal weight.

Therefore, every edge of this cycle must be in $A'$. Which contradicts the fact that A is a tree

I don't understand the conclusion in italics. This a demonstration from my teacher but it seems that it pop out without any explanation... Can you help me?

  • 2
    $\begingroup$ Is this a duplicate of this question? Here's another possible duplicate on stackoverflow that is more extensive than the first one, and here is a nice LaTeX version of the SO proof (I think). $\endgroup$ – G. Bach Nov 27 '15 at 15:59
  • $\begingroup$ Yes it is for the definition! Actually we have e and e' ut I don't know how todo it in Latex (the prime above e and not above the indice...) $\endgroup$ – Revolucion for Monica Nov 28 '15 at 23:04
  • 1
    $\begingroup$ @Marine1 Write e' ($e'$) rather than e\prime ($e\prime$). This works with subscripts, too: e'_i and e_i' both give $e'_i$, as distinct from e_{i'}, which gives $e_{i'}$. $\endgroup$ – David Richerby Nov 30 '15 at 8:43

Your Answer

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

Browse other questions tagged or ask your own question.