safe edge for Minimum spanning tree

Question

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 .

please help me out !

Answer 1

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.

Answer 2

I think the issue you having is the understanding of why A respects the cut, and you think that if (u,v) crosses the cut, then A is no longer a valid condition. In the proof when A respects the cut it doesn't imply that if we add an edge that crosses the cut, it won't be safe. Let me provide you with an informal definition of a safe edge.

("Paraphrased: A light edge that crosses a cut that respects A is safe for A.")

(taken from University of Hawaii)

So, this definition shows that When we add (u,v) to two separate unconnected parts of a graph that one of them is A and it's an MST, that edge since it's minimum( light edge ), therefore, it must be safe. This is the main argument of the proof, that needs to be shown, that the addition of light edge will result in the connections of parts of the graphs that are not connected and will keep the property of MST after that addtion.