What is the point of the "respect" requirement in cut property of minimum spanning tree?

Question

The cut property stated in terms of Theorem 23.1 in Section 23.1 of CLRS (2nd edition) is as follows.

Theorem 23.1 Let $G = (V, E)$ 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 $(S, V-S)$ be any cut of $G$ that respect $A$ (emphasis added), and let $(u,v)$ be a light edge crossing $(S,V-S)$. Then, edge $(u,v)$ is safe for $A$.

Why does this theorem require that the cut $(S,V-S)$ respect $A$? How is this requirement used in the correctness proof? I do not see what would fail if the requirement was removed.

---

Some Definitions:

• Cut: A cut $(S, V-S)$ of an undirected graph $G=(V,E)$ is a partition of $V$.
• Cross: An edge $(u,v) \in E$ crosses the cut $(S,V-S)$ if one of its endpoints is in $S$ and the other is in $V-S$.
• Respect: A cut respects a set $A$ of edges if no edge in $A$ crosses the cut.
• Light edge: An edge is a light edge crossing a cut if its weight is the minimum of any edge crossing the cut.

Answer 1

I don't have the book handy. I assume that

1. "safe" means that $(u,v)$ can be added to $A$ and we get another subset of a minimal spanning tree of $G$, and
2. the goal is a correctness proof of Prim's algorithm¹.

Now, say the cut did not "respect" $A$. That means that there already is an edge in $A$ that crosses it. By choosing a second edge from that cut -- which may happen even with pairwise distinct weights! -- we may introduce a cycle and lose the tree property.

By requiring that the cut "respects" $A$ we know that $A \subseteq S$ and we can not introduce a cycle².

The assumptions of this theorem may be stronger than strictly necessary -- as long as we do not create a cycle, we do not per se need to care about other edges in the cut -- but we can build an algorithm around them, so the theorem is a convenient way to ensure its correctness.

---

1. Note how the theorem directly implies that fact since Prim's algorithm maintains such a cut and chooses light edges from it to grow the tree.
2. In the algorithm, we'll always have $A=S$.

Answer 2

Besides the effect of "avoiding cycles" pointed out by @Raphael, the "respect" requirement in the cut property guarantees that $A \cup \{ (u,v) \}$ is included in the minimum spanning tree $T' = T - \{ (x,y) \} \cup \{ (u,v) \}$ constructed in the correctness proof.

Since $A \subseteq T$, to ensure that $A \cup \{ (u,v) \} \subseteq T' = T - \{ (x,y) \} \cup \{ (u,v) \}$, it requires $\{ (x,y) \} \notin A$; see the figure above (Fig 23.3 in CLRS).

$(x,y) \notin A$ holds because $(x,y)$ is chosen as the edge that is on the unique path from $u$ to $v$ in $T$ and crosses the cut $(S, V-S)$ and that $A$ respects the cut $(S,V-S)$.