[proofplan] Give every directed edge capacity $1$ and compare three quantities: the maximum value of an integral $s$-$t$ [flow](/page/Flow), the maximum number of edge-disjoint directed $s$-$t$ [paths](/page/Path), and the minimum size of an edge set separating $s$ from $t$. The integral [max-flow min-cut theorem](/theorems/2568) identifies the first quantity with the minimum capacity of a source-sink cut. Unit capacities make cut capacity equal to the number of cut edges, and a reachability argument shows that minimum source-sink cuts have exactly the same size as minimum separating edge sets. [/proofplan]

[step:Turn the directed graph into a unit-capacity network] Define the capacity function $c:E \to \{1\}$ by $c(e)=1$ for every directed edge $e\in E$. An $s$-$t$ [flow](/page/Flow) in this network is a function $f:E \to [0,\infty)$ such that $0 \le f(e) \le 1$ for every $e \in E$ and such that, for every vertex $v \in V \setminus \{s,t\}$, \begin{align*} \sum_{e=(v,w)\in E} f(e) = \sum_{e=(u,v)\in E} f(e). \end{align*} Its value is \begin{align*} |f| = \sum_{e=(s,w)\in E} f(e) - \sum_{e=(u,s)\in E} f(e). \end{align*} For a subset $S \subseteq V$ with $s \in S$ and $t \notin S$, define the directed [cut](/page/Cut) \begin{align*} \delta^+(S) = \{(u,v)\in E : u \in S,\ v \in V \setminus S\}. \end{align*} Since every edge has capacity $1$, the capacity of this cut is $|\delta^+(S)|$. [/step]

[step:Identify integral unit flows with edge-disjoint directed paths]We claim that the maximum value of an integral $s$-$t$ [flow](/page/Flow) is equal to the maximum number of pairwise edge-disjoint directed [paths](/page/Path) from $s$ to $t$. First, suppose $P_1,\dots,P_m$ are pairwise edge-disjoint directed paths from $s$ to $t$. Define $f:E \to \{0,1\}$ by setting $f(e)=1$ when $e$ belongs to one of $P_1,\dots,P_m$, and setting $f(e)=0$ otherwise. Edge-disjointness gives $f(e)\le 1$ for every $e\in E$. At every vertex $v\in V\setminus\{s,t\}$, every occurrence of $v$ on one of the directed paths contributes exactly one incoming edge and exactly one outgoing edge of that same path; summing over the paths gives flow conservation at $v$. The value of $f$ is $m$, because each path contributes one net unit out of $s$. Conversely, let $f:E\to\{0,1\}$ be an integral $s$-$t$ flow of value $k$. We prove by induction on $k$ that the support \begin{align*} E_f=\{e\in E:f(e)=1\} \end{align*} contains $k$ pairwise edge-disjoint directed paths from $s$ to $t$. If $k=0$, there is nothing to prove. Assume $k\ge 1$. Let $R\subseteq V$ be the set of vertices reachable from $s$ by a directed path using only edges in $E_f$. If $t\notin R$, then no edge of $E_f$ leaves $R$ by definition of $R$. Define the outgoing boundary edge set $A_{\mathrm{out}}=\{e=(u,v)\in E : u\in R,\ v\notin R\}$ and the incoming boundary edge set $A_{\mathrm{in}}=\{e=(u,v)\in E : u\notin R,\ v\in R\}$. Summing the flow-conservation identities over all vertices in $R\setminus\{s\}$ gives \begin{align*} \sum_{e\in A_{\mathrm{out}}} f(e) - \sum_{e\in A_{\mathrm{in}}} f(e) = k. \end{align*} The first sum is $0$, while the second sum is nonnegative, a contradiction. Hence $t\in R$, so there is a directed path $P$ from $s$ to $t$ whose every edge lies in $E_f$. Define $f_P:E\to\{0,1\}$ to be the indicator function of the edge set of $P$, and set $f_1=f-f_P$. Then $f_1:E\to\{0,1\}$ is an integral $s$-$t$ flow of value $k-1$. By the induction hypothesis, $f_1$ contains $k-1$ pairwise edge-disjoint directed $s$-$t$ paths. Together with $P$, these give $k$ pairwise edge-disjoint directed $s$-$t$ paths.[/step]

[guided]The point of this step is to justify that a unit integral flow is not merely analogous to a collection of paths; it actually decomposes into edge-disjoint paths. Start with pairwise edge-disjoint directed paths $P_1,\dots,P_m$ from $s$ to $t$. Define a function $f:E \to \{0,1\}$ by setting $f(e)=1$ when $e$ belongs to one of $P_1,\dots,P_m$, and setting $f(e)=0$ otherwise. Because the paths are edge-disjoint, no edge is counted twice, so $f(e)\le 1=c(e)$ for every $e\in E$. At an intermediate vertex $v\in V\setminus\{s,t\}$, every time one of the paths enters $v$, the same path later leaves $v$ along exactly one outgoing edge. Thus the total incoming contribution and total outgoing contribution at $v$ are equal, so $f$ satisfies flow conservation. At $s$, each of the $m$ paths contributes one net unit leaving $s$, and therefore $|f|=m$. Now suppose instead that $f:E\to\{0,1\}$ is an integral $s$-$t$ flow of value $k$. Define its support by \begin{align*} E_f=\{e\in E:f(e)=1\}. \end{align*} We show that $E_f$ contains $k$ edge-disjoint directed paths from $s$ to $t$. The proof is by induction on $k$. For $k=0$, the assertion is empty. Assume $k\ge 1$, and let $R\subseteq V$ be the set of all vertices reachable from $s$ using only edges in $E_f$. Why must $t$ lie in $R$? If $t\notin R$, then no edge of $E_f$ can leave $R$, because such an edge would make its head reachable. Summing the conservation law over all vertices of $R\setminus\{s\}$ cancels every edge with both endpoints in $R$, leaving only boundary terms: \begin{align*} \sum_{e=(u,v)\in E,\ u\in R,\ v\notin R} f(e) - \sum_{e=(u,v)\in E,\ u\notin R,\ v\in R} f(e) = k. \end{align*} The first sum is $0$, since no positive-flow edge leaves $R$. The second sum is nonnegative. Hence the left-hand side is at most $0$, contradicting $k\ge 1$. Therefore $t\in R$, so there is a directed $s$-$t$ path $P$ contained in $E_f$. Let $f_P:E\to\{0,1\}$ be the indicator function of the edge set of $P$, and define $f_1=f-f_P$. Since every edge of $P$ lies in $E_f$, the function $f_1$ still takes values in $\{0,1\}$. Subtracting one directed $s$-$t$ path preserves flow conservation at every intermediate vertex and lowers the value by exactly $1$, so $f_1$ is an integral $s$-$t$ flow of value $k-1$. The induction hypothesis gives $k-1$ edge-disjoint directed $s$-$t$ paths in the support of $f_1$, and adding $P$ gives $k$ such paths in the support of $f$.[/guided]

[step:Relate source-sink cuts to separating edge sets] For every $S\subseteq V$ with $s\in S$ and $t\notin S$, the edge set $\delta^+(S)$ separates $s$ from $t$. Indeed, any directed path from $s$ to $t$ starts in $S$ and ends in $V\setminus S$, so it has a first edge whose tail lies in $S$ and whose head lies in $V\setminus S$; that edge belongs to $\delta^+(S)$. Conversely, let $F\subseteq E$ be an edge set such that $(V,E\setminus F)$ contains no directed path from $s$ to $t$. Let $R\subseteq V$ be the set of vertices reachable from $s$ in the directed graph $(V,E\setminus F)$. Then $s\in R$ and $t\notin R$. If an edge $e=(u,v)\in\delta^+(R)$ were not in $F$, then $e\in E\setminus F$, and since $u$ is reachable from $s$ in $(V,E\setminus F)$, the vertex $v$ would also be reachable from $s$ in $(V,E\setminus F)$, contradicting $v\notin R$. Hence $\delta^+(R)\subseteq F$, and therefore \begin{align*} |\delta^+(R)|\le |F|. \end{align*} Thus the minimum size of a separating edge set is equal to \begin{align*} \min\{|\delta^+(S)| : S\subseteq V,\ s\in S,\ t\notin S\}. \end{align*} [/step]

[step:Apply the integral max-flow min-cut theorem] By the [Integral Max-Flow Min-Cut Theorem](/theorems/???) for finite networks with integral capacities, there exists a maximum $s$-$t$ flow whose values are integers, and its value equals the minimum capacity of an $s$-$t$ cut. In the present network all capacities are $1$, so this common value is \begin{align*} \min\{|\delta^+(S)| : S\subseteq V,\ s\in S,\ t\notin S\}. \end{align*} By the previous step, this is the minimum cardinality of an edge set whose deletion separates $s$ from $t$. By the path-flow equivalence proved above, the same value is the maximum number of pairwise edge-disjoint directed paths from $s$ to $t$. Therefore the two quantities in the theorem statement are equal. [/step]