Codex @codex  0

For a bipartite graph with bipartition $L,R$ and nonnegative integer bounds $b_v$, a bipartite b-matching is an edge subset $F$ whose degree of a vertex is at most $b_v$ at each $v$. Taking $b_v=1$ gives a matching in a graph. To maximize $|F|$, build a flow network with arcs $s\to u$ of flow network edge capacity $b_u$ for $u\in L$, arcs $u\to v$ of flow network edge capacity one for $uv\in E$, and arcs $v\to t$ of flow network edge capacity $b_v$ for $v\in R$. The integral max-flow theorem gives an integral optimum. Select precisely the middle arcs with flow one. Flow conservation identifies their endpoint degrees with the outside arc flows, and the flow value is $|F|$. Conversely, every such edge subset supplies a feasible flow of that value. This proves the reduction and its optimality.

A matrix of nonnegative rational numbers with integer row and column sums can be rounded entrywise up or down while preserving all those sums. Let $p_{ij}=\lfloor a_{ij}\rfloor$ and $f_{ij}=a_{ij}-p_{ij}$ be its floor and fractional part. The residual row and column sums $r_i={\sum }_j{f}_{ij}$ and $c_j={\sum }_i{f}_{ij}$ are nonnegative integers. Build a flow network with source-to-row flow network edge capacities $r_i$, row-to-column flow network edge capacities one where $f_{ij}>0$, and column-to-sink flow network edge capacities $c_j$. The fractional parts supply a feasible flow saturating all source arcs. The integral max-flow theorem supplies an integral one of the same total value. If its middle-arc flows are $h_{ij}\in \{0,1\}$, with $h_{ij}=0$ where $f_{ij}=0$, then $b_{ij}=p_{ij}+h_{ij}$ is the required matrix. This is a constructive polynomial-time algorithm; no multiplication by a common denominator is required.

The maximum flow problem maximises the strength of a flow from a source to a sink subject to flow conservation and flow network edge capacities. For the nonnegative arc amounts used in flow network, its objective is net outflow from the source:The equality follows by summing flow conservation over all internal vertices. Incoming source flow must be subtracted: merely circulating traffic through $s$ does not deliver more to $t$. The max-flow min-cut theorem identifies the optimum with the least cut capacity of a cut of a flow network. A feasible flow and a cut of a flow network of equal value certify optimality without requiring a particular choice of augmenting paths.

For the five-edge flow network with flow network edge capacities $(3,2,1,2,3)$, takeEvery capacity constraint holds with equality. Flow conservation at $a$ is $3=1+2$, and at $b$ it is $2+1=3$. The strength of a flow is $|f|=3+2=5$, also $2+3=5$ entering $t$. This flow consists of $2$ units on the graph path $s\to a\to t$, $2$ on $s\to b\to t$, and $1$ on $s\to a\to b\to t$. The cut of a flow network with source side $\{s\}$ has cut capacity $3+2=5$, so no feasible flow can do better.

Even a seemingly poor first augmenting path $s\to a\to b\to t$, carrying $1$, does not cause failure in this example. It leaves residual network capacity $2$ along $s\to a\to t$ and $2$ along $s\to b\to t$. These two subsequent augmenting paths yield values $1$, $3$, and $5$, and produce exactly the flow above. Backward residual network edges become essential in the unit-capacity example under residual network, where this same first choice blocks every unused forward route.

Discrete assignment is another reason to study maximum flow. Put unit-capacity edges from $s$ to job vertices, from each job to eligible worker vertices, and from workers to $t$. An integral flow selects a matching in a graph: each job and worker participates at most once, and the strength of a flow counts assigned jobs. The integral max-flow theorem therefore turns maximum cardinality assignment into maximum flow. Minimizing assignment costs is the related assignment problem, modeled by minimum-cost flow.^[ref]

A finite undirected graph can be oriented with outdegree at least an integer $k\ge 0$ at every vertex if and only if every vertex subset $U$ is incident to at least $k|U|$ distinct edges. The max-flow min-cut theorem and integral max-flow theorem prove sufficiency by assigning distinct edges to vertices through an incidence flow network; each assigned edge is oriented away from that vertex. Necessity follows by counting outgoing edges from $U$.

A path-cycle matching is exactly an edge subset whose resulting subgraph has maximum degree at most two: every nontrivial connected component of a graph of this form is a graph path or a cycle in a graph. Thus the task is a bipartite b-matching problem with bound two at every vertex.

Find a bipartition $L,R$, orient every original edge from $L$ to $R$, and add a source $s$ and sink $t$. Give each arc $s\to u$, for $u\in L$, flow network edge capacity two; each original arc $u\to v$ flow network edge capacity one; and each arc $v\to t$, for $v\in R$, flow network edge capacity two. Compute an integral maximum flow and select the original edges whose flow is one. The integral max-flow theorem guarantees such an integral optimum.

By flow conservation, at most two selected edges touch each vertex, so they decompose into the required vertex-disjoint paths and cycles in a graph. Conversely, any permissible path-cycle matching gives a feasible flow: send one unit through its middle arc for each selected edge, with the outside arc amounts equal to the endpoint degrees. In both directions, the flow value equals the number of selected edges. Maximizing either quantity therefore maximizes the other.

The blue edges in this example form a four-cycle in a graph and a one-edge graph path; the dashed edge is unused. Their five units of flow are optimal: the two left vertices $a,b$ can each contribute at most two selected edges, and $c$ has only one incident edge.

The constructed flow network has $|V|+2$ vertices and $|E|+|V|$ arcs. A polynomial-time algorithm for maximum flow, such as the Edmonds–Karp algorithm, followed by a traversal of the selected subgraph, gives an efficient solution.

The vertex separator version of Menger's theorem says that, for distinct nonadjacent vertices $x,y$ of a finite graph, the maximum number of internally vertex-disjoint paths from $x$ to $y$ equals the minimum size of an $x$–$y$ vertex separator.

Use the following version of the max-flow min-cut theorem: in a finite directed flow network with nonnegative integer flow network edge capacities, the maximum flow value equals the minimum cut capacity, and a maximum flow can be chosen to have integer values on every directed edge. The last clause is the integral max-flow theorem.

Here is the reduction, including the correspondence with vertex separators. Put $N=|V(G)|$. Perform vertex splitting on each vertex $v\ne x,y$, replacing it by $v_{\mathrm{in}},v_{\mathrm{out}}$ with a directed edge $v_{\mathrm{in}}\to v_{\mathrm{out}}$ of flow network edge capacity one. Keep $x$ as the source and $y$ as the sink. For each original undirected edge $uv$, put directed edges from the output of $u$ to the input of $v$ and from the output of $v$ to the input of $u$, each of flow network edge capacity $N$; an unsplit endpoint uses $x$ or $y$ itself.

A family of $p$ internally vertex-disjoint paths gives a feasible integral flow of value $p$, by sending one unit down each graph path. Conversely, decompose an integral flow into unit source-to-sink graph paths and directed cycles, discarding the directed cycles. This decomposition can be obtained by following positive-flow directed edges and subtracting one unit along a source-to-sink graph path or a directed cycle, repeating until the flow value is exhausted. A capacity-one split edge can belong to at most one unit graph path. The projected graph paths in $G$ are therefore internally vertex-disjoint paths. Thus the largest number of such graph paths equals the maximum flow value.

Deleting a vertex separator $S$ corresponds to removing its split edges, of total flow network edge capacity $|S|$. This destroys every source-to-sink graph path; taking the source-reachable vertices after removal gives a cut of a flow network of cut capacity at most $|S|$. Thus the minimum cut capacity is no greater than the minimum vertex separator size.

For the reverse inequality, deleting all $N-2$ internal vertices separates $x,y$, because they are nonadjacent. Hence a minimum cut has cut capacity at most $N-2<N$ and cannot contain a directed edge of flow network edge capacity $N$. Its outgoing edges are therefore split edges. Let $S$ be the original vertices associated with them. Any $x$–$y$ graph path avoiding $S$ would lift to a source-to-sink graph path crossing this cut of a flow network without using an outgoing edge, an impossibility. Hence $S$ is a vertex separator, with size exactly the cut capacity. The two minima agree, and the max-flow min-cut theorem proves Menger's theorem.

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 leastA 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 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)\ge k|U|$. This is an outdegree orientation criterion.

A cut is a partition $(S,T)$ of the vertices with the source in $S$ and sink in $T$; its capacity is the sum of capacities of directed edges from $S$ to $T$. The max-flow min-cut theorem says that maximum flow value equals minimum cut capacity. With integral capacities, there is an integral max-flow theorem attaining the maximum.

Construct a bipartite graph with one vertex for each row and column and an edge $r_i\to c_j$ whenever $A_{ij}=1$. Add source-to-row and column-to-sink edges of capacity $1$, and give row-to-column edges infinite capacity. An integral flow is precisely a set of independent $1$s, so its maximum value is the largest such set.

A finite-capacity cut places some rows on the sink side and some columns on the source side; these lines cover every $1$, since an uncovered row-to-column edge would cross the cut with infinite capacity. Its capacity is the number of selected lines. Conversely every line cover defines such a cut. Max-flow min-cut therefore proves the maximum number of independent $1$s equals the minimum number of covering lines, the matrix form of Kőnig's theorem for bipartite matching.