 Cut of a flow network

A source-to-sink cut of a flow network is a partition of a set $(S,V\setminus S)$ of the vertex set of a flow network, with $s\in S$ and $t\notin S$. Its cut capacity sums the flow network edge capacities of directed edges leaving $S$.^[ref]

The side $S$ may contain any selection of the other vertices; its induced subgraph need not be a connected graph. For the five-edge flow network with flow network edge capacities $(c_{sa},c_{sb},c_{ab},c_{at},c_{bt})=(3,2,1,2,3)$, $S=\{s\}$ gives the partition of a set $(\{s\},\{a,b,t\})$. Only $s\to a$ and $s\to b$ leave this side, so its cut capacity is $3+2=5$. Choosing $S=\{s,b\}$ instead puts $a\to b$ across the boundary in the incoming direction: its flow network edge capacity is excluded.

The left panel pairs a feasible flow of flow value $5$ with a cut of a flow network of cut capacity $5$, proving that each is optimal. The right panel uses the same feasible flow but a different cut of a flow network: the outward flow is $3+3=6$ and the backward flow is $1$, giving net flow $6-1=5$. That cut capacity is $6$, so it supplies a valid but less sharp bound. The dashed boundary marks a partition of a set, rather than an additional edge or a proposed route.