# Do $s$-$t$ cuts partition contingent vertices?

The definition of an $s$-$t$ cut is a partition of the set of vertices $V$ into $2$ sets $(A, B)$ with $s$ in $A$ and $t$ in $B$. My understanding of set partitions is that the positioning of elements in the graph does not matter.

However, if this is the correct notion of partitioning, then can construct a pathological example. Consider the following network. $$s \to B_1 \to A_1 \to B_2 \to A_2 \to t.$$Let each of the edges have a capacity of $1$. Then the max flow is clearly $1$. If we let the $s$-$t$ cut be such that set $A$ consists of $s$, $A_1$ and $A_2$, and $B$ is the rest, then the capacity of the cut is $3$ since there is a flow of value $1$ exiting each of the $3$ vertices in $A$. This contradicts the max-flow-min-cut theorem.

Is my understanding right then that the $s$-$t$ cut is not a partition of a set but a graph? By this I mean, that the resultant two sets have to be contiguous?

• What do you mean by "the positioning of elements in the graph does not matter"? – David Richerby Dec 31 '14 at 12:55

The example is correct: in this $s$-$t$ cut the capacity of the cut is indeed $3$. However, the min-cut in the max-flow min-cut theorem talks about the capacity of the minimum $s$-$t$ cut. So one must take an $s$-$t$ cut that gives minimum capacity: what you have in your example is not one of them.