Do these sentences in "Algorithms 4th Edition" contain an errata? ("Algorithms 4th Edition" by Robert Sedgewick and Kevin Wayne)

Question

I am reading "Algorithms 4th Edition" by Robert Sedgewick and Kevin Wayne.

I am reading a section about Network-flow algorithms

Recall from SECTION 4.3 that a cut in a graph is a partition of the vertices into two disjoint sets, and a crossing edge is an edge that connects a vertex in one set to a vertex in the other set. For flow networks, we refine these definitions as follows:

Definition. An $st$-cut is a cut that places vertex $s$ in one of its sets and vertex $t$ in the other.

Each crossing edge corresponding to an $st$-cut is either an $st$-edge that goes from a vertex in the set containing $s$ to a vertex in the set containing $t$, or a $ts$-edge that goes in the other direction. We sometimes refer to the set of crossing $st$-edges as a cut set. The capacity of an $st$-cut in a flow network is the sum of the capacities of that cut's $st$-edges, and the flow across an $st$-cut is the difference between the sum of the flows in that cut's $st$-edges and the sum of the flows in that cut's $ts$-edges. Removing all the $st$-edges (the cut set) in an $st$-cut of a network leaves no path from $s$ to $t$, but adding any one of them back could create such a path.

Removing all the $st$-edges ($=\{e_1,e_3,e_4\}$) in an $st$-cut of the following network leaves no path from $s$ to $t$, and adding $e_1$ back cannot create such a path.

Do the above sentences in "Algorithms 4th Edition" contain an errata?

Answer 1

There's a couple of ways you could read that sentence, so (as mentioned in the comments) Sedgewick and Wayne are not necessarily making a false claim. Regardless, it is the case that:

1. In an arbitrary $s-t$ cut, as the example in the question shows, not every edge in the cut set is part of an $s-t$ path.
2. However, whenever an edge in the cut set is not part of an $s-t$ path, this can be exploited to generate a smaller cut. So in the minimum cut, every edge in the cut set will be part of an $s-t$ path.

We are usually most concerned with the minimum cut, so we don't have to worry about this issue too much either way.

To prove claim 2, let $(S,T)$ be the partition defining the cut, and let $vw$ be an edge in the cut set such that there is no $s-t$ path using $vw$ and no other edge in the cut set. Then let $W$ be the set of vertices in the subgraph $G[T]$ reachable from $w$, and define the new cut $(S \cup W, T - W)$. By construction, there are no edges from $W$ to $T-W$, so the cut set does not gain any new edges. However, edge $vw$ is removed from the cut set, so the new cut has a lower capacity. Similarly, if there is no $s-v$ path in $G[S]$, then let $V$ be the set of all vertices in the subgraph $G[S]$ that can reach $v$, and define the new cut set $(S - V, T \cup V)$; this will have lower capacity by the same argument.