Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 3 / 19H / b / i / Solution

Label the seven black intermediate vertices, from left to right and top to bottom within each column, by $a,b,c,d,e,f,g$: thus $a$ is directly below $r$, $b$ is the lower-left vertex, $c,d$ are the next upper and lower vertices, $e$ is the middle-right vertex, and $f,g$ are the upper-right and lower-right vertices.

For $x=4$, the following nonzero edge flows are feasible:Their value is $9$. The cut with source side $\{s\}$ has capacityBy the max-flow min-cut theorem,