[proofplan] We encode the flow-balance equations by the directed incidence matrix and add one formal arc from $t$ to $s$, so that the value variable $\nu$ becomes an ordinary arc-flow variable in an augmented incidence matrix. Directed incidence matrices are totally unimodular by a determinant expansion argument. After deleting one redundant balance row, replacing equalities by pairs of inequalities, and adjoining capacity and non-negativity bounds, the full constraint matrix remains totally unimodular. Finally, every vertex of a polyhedron with totally unimodular constraint matrix and integral right-hand side is integral, and a bounded maximum-flow linear program has an optimal vertex. [/proofplan] [step:Encode the flow equations as an augmented incidence system] For each vertex $v\in V$, let $e_v\in \mathbb{Z}^{V}$ denote the standard coordinate vector indexed by $V$, with $(e_v)_v=1$ and $(e_v)_w=0$ for $w\neq v$. Define the directed incidence matrix $M\in \mathbb{Z}^{V\times A}$ by declaring that, for an arc $a=(p,q)\in A$, the entries of the column indexed by $a$ are $M_{p,a}=1$, $M_{q,a}=-1$, and $M_{v,a}=0$ for every $v\in V\setminus\{p,q\}$. This is well-defined because the theorem statement assumes that no arc is a loop, so $p\neq q$. Thus the balance equations in the statement are exactly \begin{align*} Mx-\nu(e_s-e_t)=0. \end{align*} Since the theorem statement assumes $s\neq t$, the formal additional arc $a_0=(t,s)$ is not a loop. Introduce this arc, and define the augmented arc set $A_0:=A\cup\{a_0\}$. Let $B\in \mathbb{Z}^{V\times A_0}$ be the directed incidence matrix of the augmented directed graph $(V,A_0)$, with the same sign convention as $M$. The column of $B$ indexed by $a_0=(t,s)$ is $e_t-e_s$. If we define \begin{align*} z\in \mathbb{R}^{A_0}, \qquad z_a=x_a\text{ for }a\in A,\qquad z_{a_0}=\nu, \end{align*} then the flow-balance equations become \begin{align*} Bz=0. \end{align*} Indeed, the $A$-columns contribute $Mx$, and the $a_0$-column contributes $\nu(e_t-e_s)=-\nu(e_s-e_t)$. [/step] [step:Prove that the augmented incidence matrix is totally unimodular] We first record the elementary determinant criterion for directed incidence matrices. Let $Q$ be any square submatrix of $B$. We prove that $\det Q\in\{-1,0,1\}$ by induction on the size of $Q$. If $Q$ has size $1$, then its single entry is one of $-1,0,1$, so the claim holds. Assume the claim for all smaller square submatrices. If some column of $Q$ has no nonzero entries, then $\det Q=0$. If some column of $Q$ has exactly one nonzero entry, equal to $\varepsilon\in\{-1,1\}$, then expanding $\det Q$ along that column gives $\det Q=\pm \varepsilon\, \det Q'$, where $Q'$ is a smaller square submatrix of $B$. By the induction hypothesis, $\det Q'\in\{-1,0,1\}$, hence $\det Q\in\{-1,0,1\}$. It remains to consider the case in which every column of $Q$ has at least two nonzero entries. Since each column of the directed incidence matrix $B$ has exactly one $1$ and exactly one $-1$, every column of $Q$ then has exactly those two nonzero entries. Therefore the sum of the rows of $Q$ is the zero row. The rows of $Q$ are linearly dependent, so $\det Q=0$. Thus every square subdeterminant of $B$ belongs to $\{-1,0,1\}$, and $B$ is totally unimodular. [/step] [step:Build a totally unimodular inequality description of the flow polyhedron] Choose one vertex $r\in V$, and let \begin{align*} B_r\in \mathbb{Z}^{(V\setminus\{r\})\times A_0} \end{align*} be the matrix obtained from $B$ by deleting the row indexed by $r$. Since deleting rows preserves total unimodularity, $B_r$ is totally unimodular. Moreover, the equation $B_rz=0$ is equivalent to $Bz=0$: each column of $B$ has row-sum $0$, so if all rows except the $r$-row vanish on $z$, then the $r$-row also vanishes on $z$. Define $I_A$ to be the $A\times A_0$ matrix whose row indexed by $a\in A$ has a single $1$ in the column indexed by $a$ and has $0$ in every other column, including the $a_0$-column. Define the constraint matrix $C$ to be the matrix obtained by stacking, from top to bottom, the four row blocks $B_r$, $-B_r$, $I_A$, and $-I_A$. Define the right-hand side vector $d\in \mathbb{Z}^{2|V|-2+2|A|}$ to be the vector whose four corresponding blocks are $0$, $0$, $u$, and $0$, where $u\in\mathbb{Z}_{\geq 0}^{A}$ is the capacity vector with coordinate $u_a$ on the row indexed by $a\in A$. Then the original feasible region is exactly \begin{align*} P:=\{z\in\mathbb{R}^{A_0}: Cz\leq d\}. \end{align*} The first two block inequalities impose $B_rz=0$, the third block imposes $z_a\leq u_a$ for $a\in A$, and the fourth block imposes $z_a\geq 0$ for $a\in A$. The matrix $C$ is totally unimodular. Row sign changes preserve total unimodularity because they multiply every affected determinant by $-1$. Repeating a row up to sign preserves total unimodularity because any square submatrix containing both a row and its signed duplicate has determinant $0$, while any square submatrix containing at most one copy is a signed square submatrix of the original matrix. Finally, adjoining the rows of $I_A$ and $-I_A$ preserves total unimodularity by induction on the number of adjoined rows: if a square submatrix contains an adjoined unit row, expansion along that row reduces its determinant to a square subdeterminant of the previously constructed matrix; if it contains no adjoined unit row, it is already covered. Hence $C$ is totally unimodular. [/step] [step:Apply total unimodularity to obtain an integral optimal vertex] The polyhedron $P$ is nonempty because $z=0$ is feasible. It is bounded: for every original arc $a\in A$ one has $0\leq z_a\leq u_a$, and, because $s\neq t$, the balance equation at $s$ gives \begin{align*} z_{a_0}=\nu=\sum_{a=(s,w)\in A} z_a-\sum_{a=(w,s)\in A} z_a. \end{align*} The graph is finite and each original arc coordinate is bounded by its capacity, so $\nu$ is bounded by a finite sum of the capacities $u_a$. Therefore $P$ is a nonempty compact polytope. Since a compact polytope is the convex hull of its vertices and the affine map $z\mapsto z_{a_0}$ is maximized over a convex hull at one of its extreme points, the objective attains its maximum at some vertex $z^*$ of $P$. Let $I$ be the set of active inequalities at $z^*$: \begin{align*} I:=\{i: C_i z^*=d_i\}, \end{align*} where $C_i$ denotes the $i$-th row of $C$ and $d_i$ the corresponding component of $d$. Since $z^*$ is a vertex of $P$, the active row vectors $\{C_i:i\in I\}$ span $\mathbb{R}^{A_0}$. Hence there is a subset $J\subset I$ with $|J|=|A_0|$ such that the square matrix \begin{align*} C_J\in \mathbb{Z}^{A_0\times A_0} \end{align*} formed by the rows indexed by $J$ is nonsingular. Because $C$ is totally unimodular, $\det C_J\in\{-1,1\}$. Since $z^*$ satisfies the active equations indexed by $J$, we have \begin{align*} C_Jz^*=d_J, \end{align*} where $d_J\in\mathbb{Z}^{A_0}$ is the corresponding subvector of $d$. By [Cramer's rule](/theorems/3305), each coordinate of $z^*$ is a quotient of two integers whose denominator is $\det C_J=\pm 1$. Therefore \begin{align*} z^*\in \mathbb{Z}^{A_0}. \end{align*} Writing $x_a^*:=z_a^*$ for $a\in A$ and $\nu^*:=z_{a_0}^*$ gives an optimal feasible flow with every $x_a^*\in\mathbb{Z}$ and $\nu^*\in\mathbb{Z}$. [guided] The final step is the bridge from total unimodularity to integrality of the maximum flow. Recall the construction used in the preceding steps. The augmented arc set is $A_0=A\cup\{a_0\}$ with $a_0=(t,s)$, and the variable $z\in\mathbb{R}^{A_0}$ is defined by $z_a=x_a$ for $a\in A$ and $z_{a_0}=\nu$. The matrix $B_r$ is obtained from the augmented incidence matrix by deleting one row, $I_A$ selects the original arc coordinates, and $C$ is obtained by stacking $B_r$, $-B_r$, $I_A$, and $-I_A$. The right-hand side $d$ has corresponding blocks $0$, $0$, $u$, and $0$. The previous determinant argument proves that this matrix $C$ is totally unimodular, and the capacity hypothesis gives $d\in\mathbb{Z}^{2|V|-2+2|A|}$. Thus the feasible region is \begin{align*} P=\{z\in\mathbb{R}^{A_0}: Cz\leq d\}, \end{align*} where $C$ is totally unimodular and $d$ is integral. The point $z=0$ belongs to $P$, so the feasible region is nonempty. For each original arc $a\in A$, the inequalities in $Cz\leq d$ give \begin{align*} 0\leq z_a\leq u_a. \end{align*} The remaining coordinate is $z_{a_0}=\nu$. It is also bounded, because $s\neq t$ and the balance equation at the source $s$ expresses it as \begin{align*} z_{a_0}=\nu=\sum_{a=(s,w)\in A} z_a-\sum_{a=(w,s)\in A} z_a. \end{align*} Each term on the right-hand side is bounded between $0$ and its capacity, and there are only finitely many arcs. Thus $P$ is a nonempty bounded polyhedron, hence a compact polytope. By the finite-dimensional polytope theorem, $P$ is the convex hull of its vertices. An affine function on a convex hull takes its maximum at a vertex whenever it attains a maximum: if a maximizer is written as a convex combination of vertices, at least one vertex in that combination has objective value no smaller. Therefore the linear objective $z\mapsto z_{a_0}$ has an optimal solution that is a vertex of $P$. Now let $z^*$ be such an optimal vertex. The defining property of a vertex is that the active constraints determine the point uniquely. Formally, let \begin{align*} I:=\{i: C_i z^*=d_i\} \end{align*} be the set of active inequalities. If the active rows did not span $\mathbb{R}^{A_0}$, there would exist a nonzero vector $h\in\mathbb{R}^{A_0}$ with \begin{align*} C_i h=0 \quad \text{for every } i\in I. \end{align*} For sufficiently small $\varepsilon>0$, the points $z^*+\varepsilon h$ and $z^*-\varepsilon h$ would still satisfy all inactive strict inequalities and would keep all active inequalities equalities. Hence both points would lie in $P$, and $z^*$ would be the midpoint of two distinct feasible points, contradicting that $z^*$ is a vertex. Therefore the active rows span $\mathbb{R}^{A_0}$. Because the active rows span, we can choose a subset $J\subset I$ with exactly $|A_0|$ rows such that \begin{align*} C_J\in\mathbb{Z}^{A_0\times A_0} \end{align*} is nonsingular. Since $C$ is totally unimodular, every square subdeterminant of $C$ is $-1$, $0$, or $1$; nonsingularity excludes $0$, so \begin{align*} \det C_J\in\{-1,1\}. \end{align*} The point $z^*$ satisfies the selected active equations: \begin{align*} C_Jz^*=d_J, \end{align*} and $d_J$ is integral because the capacities $u_a$ are integral and all other right-hand sides are $0$. By Cramer's rule, the coordinate $(z^*)_k$ is \begin{align*} (z^*)_k=\frac{\det C_J^{(k)}}{\det C_J}, \end{align*} where $C_J^{(k)}$ is the integer matrix obtained from $C_J$ by replacing its $k$-th column by $d_J$. Thus $\det C_J^{(k)}\in\mathbb{Z}$ and $\det C_J=\pm 1$, so $(z^*)_k\in\mathbb{Z}$. Since this holds for every coordinate, \begin{align*} z^*\in\mathbb{Z}^{A_0}. \end{align*} Finally, the original flow variables are $x_a^*=z_a^*$ for $a\in A$, and the flow value is $\nu^*=z_{a_0}^*$. Hence the optimal flow and its value are integral. [/guided] [/step]