Given a network with a source $A$, a sink $B$, and capacities on directed arcs, define what is meant by a minimum cut.

The $m$ streets and $n$ intersections of a town are represented by sets of edges $E$ and vertices $V$ of a connected graph. A city planner wishes to make all streets one-way while ensuring it possible to drive away from each intersection along at least $k$ different streets.

Use a theorem about min-cut and max-flow to prove that the city planner can achieve his goal provided that the following is true:

$$d(U) \geqslant k|U| \text { for all } U \subseteq V,$$

where $|U|$ is the size of $U$ and $d(U)$ is the number edges with at least one end in $U$. How could the planner find street directions that achieve his goal?

[Hint: Consider a network having nodes $A, B$, nodes $a_{1}, \ldots, a_{m}$ for the streets and nodes $b_{1}, \ldots, b_{n}$ for the intersections. There are directed arcs from $A$ to each and from each $b_{i}$ to $B$. From each $a_{i}$ there are two further arcs, directed towards $b_{j}$ and $b_{j^{\prime}}$ that correspond to endpoints of street $i .]$