# safe edge for Minimum spanning tree

I know this question is posted many times, but i am still posting this because i have my own doubt which pulls me out to move forward to kruskal and prim's algorithm.So Please do help me out $-:$

## Question

Let $G=\left(V,E\right)$ be a be a connected, undirected graph with a real valued weight function $w$ defined on $E$.Let $A$ be a subset of $E$ that is included in some minimum spanning tree for $G$.Let $\left(S,V-S\right)$ be any cut of $G$ that respects $A$.Let $\left(u,v\right)$ be a light edge crossing $\left(S,V-S\right)$.Then, edge $\left(u,v\right)$ is safe for $A$.

Terminologies Used

we say that an edge $\left(u,v \right)$ crosses the cut if one of the endpoint is in $S$ and other in $V-S.$

Safe edge is edge at each step that we can add in A without violating any invariant.

we say that a Cut RESPECTS a set A of edges if no edge in A crosses the cut.

we say that an edge is a light edge satisfying a given property if its weight is the minimum of any edge satisfying the property

### MY Approach/Doubt

With the help of book, i am able to understand the proof as-:

We Assume that $T$ is a MST(Minimum Spanning tree) which do not have light edge $\left(u,v \right)$, if we can manage to construct another MST $T^{'}$which contains $\left(u,v \right)$ and have weight less than that of $T$, then we are done! i.e we have to prove that $w \left(T^{'}\right) \leq w \left(T\right)$

Consider the figure below

As MST $T$ will not contain $\left(u,v \right)$(given) ,there must be an edge that crosses the cut, otherwise it will be divided into 2 components.

Let that edge be $\left(x,y \right)$

Now let us construct the MST$T^{'}$ from $T$ by removing $\left(x,y \right)$ and adding $\left(u,v \right)$ given as-:

$$w \left(T^{'}\right)=w \left(T\right)-w \left(x,y\right)+w \left(u,v\right)$$

$\Rightarrow \left(u,v \right) \leq w \left(x,y\right)$ as $\left(u,v \right)$ is light edge

$\Rightarrow w(T^{'}) \leq w(T)$

My doubt is -:

1.Is the above proof explained above correct?am i missing something?

2.If the above proof is correct, then i have one issue .Issue is that after proving the above inequality $w(T^{'}) \leq w(T)$,the book says that $\left(u,v \right)$ is actually a safe edge for A,but is n't this contradictory?

I mean if $\left(u,v \right)$ is safe for $A$ ,then cut $\left(S,V-S\right)$ no longer respect $A$ because $\left(u,v \right)$ is an cross edge .

For a set $A$ which is a subset of some minimum spanning tree, an edge $e \notin A$ is safe if $A \cup \{e\}$ is a subset of some minimum spanning tree. In particular, if $|A| = n-2$, then any safe edge will cross the cut $(S,V-S)$. There is absolutely no requirement that $e$ not cross the cut.
• sir :my doubt is that there have to have atleast one edge $e$ which will cross the Cut $\left(S,V-S \right)$ otherwise graph will be divided into $2$ components $S$ and $V-S$ , and if edge $e$ crosses the Cut , then $A$ will no longer be safe – laura Jul 11 '17 at 16:05