So whatever gets pushed out gets pushed in.
$\begin{aligned}
&|f| \equiv f(s, V) \\
& f(s, V) + f(V - s, V) = f(V, V) = 0 \\
& f(s, V) = f(V - s, V) \\
& f(s, V) = f(V - s - t, V) + f(t, V) \\
& f(s, V) = f(t, V) - f(V - s - t, V)\\
& [\text{any vertex in $V - s - t$ is an intermediate vertex, which has 0 net flow}] \\
& f(s, V) = f(t, V) - 0 \\
& f(s, V) = f(t, V) \\
\end{aligned}$

#### § Cut:

A partition of the network into two parts, such that the source is in one
part and sink in the other. $(S, T)$ is a cut of a flow network $G$ is
a partition of $V$ such that $s \in S, t \in T$. If $f$ is a flow on $G$
then the flow across the cut is $f(S, T)$.
#### § Capacity of a cut and its relationship to flow

$c(S, T) = \sum_{s \in S, t \in T} c(s, t)$

See that we only get
**positive coefficents** here. There is no "negative capacity", only "negative flow".
#### § Theorem: upper bound flow across a cut

Value of *any* flow is upeer bounded by the capacity of *any* cut. We need
more tools to prove this, as this is basically max-flow-min-cut
#### § A different characterization of flow value

Lemma: for any flow $f$ and any cut $(S, T)$ we have that $|f| = f(S, T)$.
It's because we have the source on one side, and the sink on the other side.
That gives us the flow! Everything else cancels by conservation.
$\begin{aligned}
&f(S, T) = f(S, V) - f(S, S) \\
&f(S, T) = f(S, V) - 0 \\
&f(S, T) = f(s, V) + f(S - s, V) \\
\end{aligned}$

As $S - s$ does not contain $t$, by flow conservation, we must have that $f(S - s, V) = 0$.
Thus we get:
$\begin{aligned}
f(S, T) = f(s, V) = |f|
\end{aligned}$

So, I can know the capacity of any cut $(S, T)$ bounds the flow of the network!
So if I go look at the min-cut, then I can bound the max flow. We don't know
how to find these min-cuts. That's what we'll need to figure out.
#### § Residual network

Network that points us to locations with leftover capacity where we can
push flow. $G_f(V, E_f)$ contains all those edges that have positive (greater than zero)
residual capacity. Edges in $E_f$ admit more flow. If $(v, u) \not \in E$, then
$c(v, u) = 0$, but $f(v, u) = -f(u, v)$. So we will have extra edges in the
residual network that don't exist in the original network.
If I have a flow $-1$ due to a back-edge with capacity $0$, I can in fact
send more flow to make it $0$! So I can have "back edges" in the residual network
for edges whose flow has to shrink.
#### § Augmenting path in $G_f$

**Sid question:** A path from $s$ to $t$ in $G_f$. Why does the existence of an augmenting path in $G_f$ actually mean that we can increase the flow? even when we have "back edges"? **Sid answer**: Because at the end of the day, we are picking a path from $s$ to $t$ which tells us how to change our flow in a way that we still respect capacity constraints.