= 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:
$$
\begin{array}{c|cccccccccc}
\text{edge}&sr&rc&cf&ft&sb&bd&de&et&dg>\\ \hline
\text{flow}&4&4&4&4&5&5&3&3&2&2.
\end{array}
$$
Their value is $9$. The cut with source side $\{s\}$ has capacity
$$
C(\{s\},V\setminus\{s\})=x+5=9.
$$
By the max-flow min-cut theorem,
$$
\boxed{\delta^*(4)=9}.
$$
Back to article page
