= Solution
An <cut of a flow network> partitions a <flow network> into $S,S^c$, with source $A\in S$ and sink $B\notin S$. Its <cut capacity> is the sum of capacities of arcs directed from $S$ to $S^c$; a <minimum cut> minimizes this sum.
Use the suggested nodes. Give $A\to a_e$ capacity $1$, each $a_e\to b_v$ capacity $M=m+kn+1$, and each $b_v\to B$ capacity $k$. By the <max-flow min-cut theorem>, a flow of value $kn$ exists once every <cut capacity> is at least $kn$.
Consider a <cut of a flow network> containing no crossing arc of capacity $M$, and let $U$ be the intersections on the sink side. Every street incident to $U$ must also be on that side, or its arc to an endpoint in $U$ would cross the <cut of a flow network>. Hence at least $d(U)$ source-to-street arcs cross, as do the $n-|U|$ intersection-to-sink arcs from the other intersections. Therefore its <cut capacity> is at least
$$
d(U)+k(n-|U|)\geq kn.
$$
A <cut of a flow network> crossing a capacity-$M$ arc has still larger capacity. The <cut of a flow network> just before the sink has capacity $kn$, proving the maximum flow value is exactly $kn$.
The <integral max-flow theorem> supplies an integral maximum flow. Every intersection sends $k$ units to the sink; each street can supply at most one unit, assigned to one endpoint. Orient each assigned street \b[away from its assigned endpoint]. Orient unassigned streets arbitrarily. Then each vertex has at least $k$ outgoing streets. An <Ford-Fulkerson algorithm> with integer capacities constructs this <flow> and therefore the street directions. Notice that the condition also is necessary: outgoing streets from vertices in $U$ are distinct edges incident to $U$, so $d(U)\geq k|U|$. This is an <outdegree orientation criterion>.
Back to article page
