It remains to show that the Ford-Fulkerson algorithm actually gives us the maximum possible flow. We know a rough upper bound on the flow: the total capacity of all edges leaving the source $s$. However, this is not the best upper bound we can get.
Recall the following definition from our discussion of minimum spanning trees.
Definition 5.8. A cut is a partition of vertices into two nonempty subsets $(S,V-S)$. The cutset of a cut $S$ is the set of edges with exactly one endpoint in $S$.
Suppose we have a cut in our flow network, with $s$ in one set of the partition and $t$ in the other. We observe that the edges in the cutset that move from the $s$ side to the $t$ side constitutes a rough bound on the amount of flow that goes from $s$ to $t$. We can formalize this notion.
Definition 14.1. An $s,t$-cut is a partition $(S,T)$ of the vertex set $V$ such that $s \in S$ and $t \in T$.
One observation that we can make in the context of flows is that a cut that divides $s$ and $t$ into two different parts of the cut means that flow will necessarily travel from one side of the cut to the other. We can try to quantify some aspects of this.
Definitiom 14.2. The capacity of a cut $(S,T)$ is the capacity of all edges leaving $S$, \[c(S,T) = \sum_{(u,v) \in S \times T \subseteq E} c(u,v).\]
Example 14.3. Consider the following graph. The vertices highlighted in yellow are in the set $S$, and we consider the cut $(S,T)$. Then the capacity of this cut is the capacity of edges highlighted in cyan, $3+1+5 = 9$.
Note that the capacity of the cut is much lower than the capacity of the edges leaving the source node $s$. Intuitively, it seems like any flow is subject to the capacity of a cut. After all, all flow has to travel from one side of the cut to the other. But we can go further with this: it seems like this should be true for any cut we can define, which leads us to the following problem.
Problem 14.4. The minimum cut problem is: Given a flow network $G = (V,E,s,t,c)$, find a cut $(S,T)$ with minimum capacity.
If our intuition is correct, then finding a minimum cut will give us a possibly better upper bound on the maximum flow than the outgoing capacity of the source vertex.
Lemma 14.5. Let $f$ be a flow and $(S,T)$ be a cut. Then the value of a flow is the flow leaving $S$ less the flow entering $S$, \[v(f) = \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v).\]
Proof. Since there are no edges entering $s$, we have \[v(f) = \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) = \sum_{(s,v) \in E} f(s,v).\] By conservation, we have for all $v \in V$, \[\sum_{(u,v) \in E} f(u,v) - \sum_{(v,w) \in E} f(v,w) = 0.\] Then putting the two together, we have \begin{align*} v(f) &= \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) \\ &= \sum_{(s,v) \in E} f(s,v) - \sum_{(v,s) \in E} f(v,s) + 0 \\ &= \sum_{v \in S} \left( \sum_{(u,v) \in E} f(u,v) - \sum_{(v,w) \in E} f(v,w)\right) \\ &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v). \end{align*} $$\tag*{$\Box$}$$
Example 14.6. Consider the following flow network with cut $(S,T)$, where vertices in $S$ are highlighted in yellow and vertices in $T$ are highlighted in green. The capacities of this network are in pink, while the flow is labeled in blue. We observe that the value of the flow is 9.
The flow leaving $S$ is circled in yellow, for a total of $2+4+9$, while the flow entering $S$ is circled in blue, which totals $6$. The difference in these flows is $2+4+9-6 = 9$, which is the value of our flow.
Of course, the in-flow of $S$ is the out-flow of $T$ and the out-flow of $S$ is the in-flow of $T$, so this lemma can be reformulated in terms of $T$. This lemma leads to the following bound.
Proposition 14.7. Let $f$ be a flow and $(S,T)$ be a cut. Then $v(f) \leq c(S,T)$.
Proof. \begin{align*} v(f) &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v) \\ &\leq \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) \\ &\leq \sum_{u \in S, v \in T, (u,v) \in E} c(u,v) \\ &\leq c(S,T) \end{align*} $$\tag*{$\Box$}$$
This bound confirms our intutition above, that any cut places an upper bound on the flow for a given network. This means that the minimal cut for a network will give us the best upper bound on the maximum flow through that network.
Corollary 14.8. Let $f$ be a flow and $(S,T)$ be a cut. If $v(f) = c(S,T)$, then $f$ is a max flow and $(S,T)$ is a min cut.
Proof. We observe that for any flow $f'$, we have $v(f') \leq c(S,T) = v(f)$. We also have that for any cut $(S',T')$, $c(S',T') \geq v(f) = c(S,T)$. $$\tag*{$\Box$}$$
This leads us to the statement of the Max-Flow Min-Cut theorem.
Theorem 14.9. The value of a maximum flow is the capacity of a minimum cut.
We will use this to show that the Ford-Fulkerson algorithm is correct, by showing that we can compute the minimum cut from it.
Theorem 14.10. Let $G = (V,E,s,t,c)$ be a flow network. Then $f$ is a maxmimum flow if and only if $G_f$ contains no augmenting paths.
Proof. We will show that the following are equivalent.
$(1) \implies (2)$ is easy: this is just Corollary 14.8.
$(2) \implies (3)$ is also fairly straightforward. Suppose $G_f$ does have an augmenting path. Then we can augment $f$ and increase the flow, so $f$ wasn't a maximum flow.
So it remains to show that $(3) \implies (1)$. We have that $f$ is a flow such that $G_f$ has no augmenting paths. Then this means that not every vertex in $G_f$ is reachable from $s$, so we let $S$ be the set of vertices reachable from $s$ in $G_f$. This naturally gives us a cut $(S,T)$, since it is clear that $t \not \in S$ (otherwise, there would be an augmenting path in $G_f$).
Now, let's consider the flow on the edges in the cutset of $(S,T)$. If $(u,v)$ is an edge in $G$ with $u \in S$ and $v \in T$. This edge is not a forward edge in $G_f$, since otherwise, $v$ would have been reachable and $v \in S$. Since $(u,v)$ is not a forward edge, this means $(u,v)$ had no unused capacity by $f$, so $f(u,v) = c(u,v)$.
Next, consider an edge $(u',v')$ in $G$ with $u' \in T$ and $v' \in S$. We claim that $f(u',v') = 0$. Suppose not. Then $(v',u')$ is a backward edge in $G_f$ and $u'$ would have been reachable by $s$, which could not be the case since $u' \in T$.
Therefore, all outgoing edges of $S$ are saturated with flow and all incoming edges of $S$ are empty. By the flow value lemma, we have \begin{align*} v(f) &= \sum_{u \in S, v \in T, (u,v) \in E} f(u,v) - \sum_{u \in T, v \in S, (u,v) \in E} f(u,v) \\ &= \sum_{u \in S, v \in T, (u,v) \in E} c(u,v) - 0 \\ &= c(S,T). \end{align*} $$\tag*{$\Box$}$$
Since the Ford-Fulkerson algorithm relies on obtaining the flow for which its residual graph contains no augmenting paths, we can conclude that the flow that the Ford-Fulkerson algorithm returns is the maximum flow. But this theorem also gives us a way to compute the minimum cut of $G$.
Theorem 14.11. Let $G = (V,E,s,t,c)$ be a flow network. Given a maximum flow $f$ for $G$, we can compute a minimum $s,t$-cut in $O(m)$ time.
Proof. First, we compute the residual graph $G_f$ in $O(m)$ time. Then doing a search, we can find all vertices that are reachable from $s$ in $O(m+n) = O(m)$ time. $$\tag*{$\Box$}$$
The Max-Flow Min-Cut theorem was a part of the Ford-Fulkerson paper. But why were they interested in maximal flows? They begin their paper with the following:
The problem discussed in this paper was formulated by T. Harris as follows:
"Consider a rail network connecting two cities by way of a number of intermediate cities, where each link of the network has a number assigned to it representing its capacity. Assuming a steady state condition, find a maximal flow from one given city to the other."
This sounds innocuous and kind of boring until you remember that Ford and Fulkerson were working at RAND and you realize that the rail network referred to by Harris is the Soviet rail system and maybe they weren't necessarily as interested in maximum flows as minimum cuts.