0
$\begingroup$

I am studying the algorithm of Sollin and we recently studied a lemma:

Let be G a graph which values are diffferent on the edges.

  • We sort the edges $e_1,e_2,...e_m$ such as $v(e_i)<v(e_j)$
  • Every tree of minimal value has at least $e_1$ et $e_2$

Proof

let be A a spanning tree which doesn't have $e_1$

$A\bigcup\{e_1\}$ has a unique cycle

let be $e_i \in$ cycle, $e_i\ne e_1$ then $A\bigcup\{e_1\}-\{e_i\}$ is a tree which value is < $v(A)$ because $v(e_i)>v(e_1)$

I don't understand why would $A\bigcup\{e_1\}$ would have a unique cycle? Do you have a justification? A graphical example?

$\endgroup$
1
$\begingroup$

The proof outcomes from the definition of a tree - they are non-oriented, connected graphs with no cycles.

Lets assume that there's no cycle after adding $e1$. Let $e1$ = $(v1, v2)$. This means that before adding $e1$ there wasn't any path that connects $v1$ and $v2$, which contradicts to the connectivity of the spanning tree. On the other hand, if there was a path the connects $e1$ and $e2$ (which didn't include $(e1, e2)$) then adding this very edge will result into a cycle, which again contradicts to the definition of a tree.

$\endgroup$
2
$\begingroup$

In a tree, there is exactly one path between any pair of vertices. When you add edge e1 you close that unique path to form a unique cycle.

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