MST: Are all safe edges, light edges?

Following are some definitions from CLRS:


DEFINITIONS :

1. Cut (S ,V-S) : of an undirected graph G = (V,E) is a partition of V(as defined in CLRS Book) .You can think it as a line that divides graph into two disjoint sets of vertices on its either side.

2. Light edge:Any edge crossing a cut is light edge if its weight is the minimum of all the edge crossing the cut.Light edge is defined with respect to a particular Cut.

3. A cut Respects a set A of edges if no edge in A crosses the cut.

4. Safe edge is the edge which we can add to MST without any violation of MST's property.These are those edges which are the part of final MST.

Yes, all safe edges (edges which are part of some MST) must be the lightest edge for some partition $(S, V-S)$ of the graph. For if $e=uv$ is a safe edge, it is part of some MST $T$, and $T-e$ partitions the vertex set of the graph into two parts $(S, V-S)$, where $u \in S$ and $v \in V-S$. If $e$ was not a lightest edge between $S$ and $V-S$, then $e$ can be removed from $T$ and replaced with a lighter edge $f$, giving a tree $T-e+f$ with a smaller weight than $T$, contradicting the fact that $T$ is an MST.

As a concrete example, suppose $G$ is the path graph on vertex set $\{a,b,c\}$ and edge set $\{ab, bc\}$, with the edges $ab$ and $bc$ having weights $1$ and $2$, respectively. Then, edge $bc$ is not the lightest edge available, but it is a safe edge to add first and it is the lightest edge between $S$ and $V-S$ if we take $S = \{a,b\}$.

StackExchange Computer Science Q#74090, answer score: 5