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 networkI 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:The flow increases overallNo conservation law is broken (flow in = flow out is still obeyed)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 flow2) 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.pdfhttps://stellar.mit.edu/S/course/6/sp15/6.046J/courseMaterial/topics/topic2/lectureNotes/Network-Flow-II-Spring15/Network-Flow-II-Spring15.pdf
Why is it that the flow value can increased along an augmenting path $p$ in a residual network?
algorithms;algorithm analysis;network flow;max flow