What is the point of the "respect" requirement in cut property of minimum spanning tree? 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.
I don't have the book handy. I assume that


"safe" means that $(u,v)$ can be added to $A$ and we get another subset of a minimal spanning tree of $G$, and
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.




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.
In the algorithm, we'll always have $A=S$.