Why is it that the flow value can increased along an augmenting path $p$ in a residual network?

Question

I was learning about Max Flow and Residual Graphs and was wondering if there was a formal proof for the statement:

the flow value can increased along an augmenting path $p$ in a residual network

I was reading the slides linked at the end of question and they seem to omit the most important part of the algorithm which is proving the above claim!

Recall how a residual network is built (which can be referenced on chapter 26 of CLRS):

$$c_f(u,v) = \begin{cases} c(u,v) - f(u,v) & if (u,v) \in E, \\ f(v,u) & if (v,u) \in E \\ 0 & otherwise. \end{cases} $$ also recall that because we don't allow self loops of length 1 or 2 (i.e. if $(u,v) \in E \implies (v,u) \not \in E$, exactly one case in the above definition of residual capacity applies.

I understand that intuitively, the first case encompasses the idea of the additional flow that we can increase in the original graph (since it encompasses the amount of extra flow we can increase) and the second case is suppose to be included for allowing our algorithms to decrease the flow.i.e. sometimes it may be necessary to actually decrease the flow in some edge(s) (or increase the flow in the opposite direction) so that the overall flow increases.

Even though this ideas are clear to me, its not clear how its guaranteed that we can actually increase the overall flow in the original graph $G$ if we choose say, the minimum residual capacity in an augmenting path. In particular, its clear to me if the path only contains edges of case 1 (since increasing the flow along such a path just means increasing the flow such that we are still bellow the capacity, so its trivial to increase the flow), but the second type of edge make it confusing for me. How is it that those edges guarantee the following:

1. The flow increases overall
2. No conservation law is broken (flow in = flow out is still obeyed)
3. No capacity constraint in the original graph is obeyed.

Not sure if there are other properties to check but those are the ones I was able to think of.

---

This is what I have so far:

Let the smallest residual capacity be $c_f(p) = \min_{(u,v) \in p} \{ c_f(u,v) \}$. If we increase the flow according to it then its clear no capacity constraint is violated. Why? There are only two type of possibilities the edge could have come from:

1) The difference between a capacity and a flow 2) The opposite direction of a flow already on the network.

Consider case 1 first. If we increase the flow, then it means that we decrease difference of the capacity and a flow (i.e. the residual capacity). If this is the case, since we choose the smallest residual capacity as the amount to make the decrease, we don't risk increasing the flow to much because an increase will correspond to a increase in flow such that the flow is less that the capacity on the real network.

If on the other hand, if the edge came because it corresponded to the opposite direction of flow of an edge, then its even easier, because that means that the flow on the original graph will correspond to a decrease not an increase. Since we are decreasing we cannot violate a capacity constraint. Furthermore, since we are choosing the smallest decrease to be made, there is not risk of the flow randomly becoming negative in the original graph (which would correspond to non-sense). Hence, this can't happen either.

Therefore, the capacity constraints are not violated by this choice of change of flow on the network.

The other two conditions, seem a little harder to check. I am sort of stuck on the other two but will keep trying and if I make progress (or not) update the question.

---

I am learning flow form the following slides based on CLRS:

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-Spring15-trunc/Network-Flow-Spring15-trunc.pdf

https://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-II-Spring15/Network-Flow-II-Spring15.pdf

Answer 1

Instead of giving a formal proof I will present some intuition on why augmenting paths increase the flow. Look at the picture below. Let's go through some augmenting path, for example the one painted in black. It increases the flow by some $x$. Then go through another one (that has $c_f(p) = y$) that contains an edge which pulls back some flow (edge $(u, v)$ is present only in residual network). When the red path enters $u$, it increases the flow that comes into $u$ by $y$, but then pulls $y$ units of flow back to $v$, so $v$ can use edge from red path to push those $y$ units somewhere else. So you see that $y$ units came to $u$, $y$ units was withdrawn from $u$, $y$ units came back to $v$ and then $y$ units went through the red path. The property that income flow equals the one that goes out is preserved. Capacity constraints (flow through an edge is not greater than capacity of this edge) are also preserved, because $y$ is the smallest edge weight on the red path. As you can see, going through the red path increases overall flow by exactly $y$, because augmenting path doesn't decrease the flow anywhere, it rather redirects it in the manner described above. It's like vertex $u$ saying to vertex $v$ "Oh hey, the red path gave me some flow, maybe you ($v$) would take back some of the one you gave me and send it to someone else?". I'd say that adding "redirecting" word somehow to "augmenting path" would clear some misunderstanding about this concepct.

Having this intuition, I think that making a formal proof from it should be fairly easy.