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
    Commented Nov 27, 2015 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$ Commented Nov 28, 2015 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$ Commented Nov 30, 2015 at 8:43


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.