# Why does if A is a spanning tree which doesn't have $e_1$ then $A\bigcup\{e_1\}$ has a unique cycle?

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)
• 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?

## 2 Answers

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.

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.