# Proof of lemma for flow in residual graph

In CLRS 3'rd edition there is a Lemma 26.2 which states that:

Let $$G=(V, E)$$ be a flow network, let $$f$$ be a flow in $$G,$$ and let $$p$$ be an augmenting path in $$G_{f}$$. Define a function $$f_{p}\colon V \times V \rightarrow \mathbb{R}$$ by $$f_{p}(u, v)=\left\{\begin{array}{ll}c_{f}(p) & \text { if }(u, v) \text { is on } p \\ 0 & \text { otherwise }\end{array}\right.$$ Then, $$f_{p}$$ is a flow in $$G_{f}$$ with value $$\left|f_{p}\right|=c_{f}(p)>0$$

How would you go about proving this?

As I understand we need to check for flow conservation and capacity constraint. We know that $$c_f(p)$$ is the minimum of the residual capacities on path $$p$$ which is smaller than the capacities, hence the capacity constraint is satisfied. But how about the flow conservation constraint and proving that the flow value is in fact $$c_f(p) > 0$$?

• At a vertex $v$ the only non-zero terms in the condition of flow conservation are if $v$ is a vertex of $p$ and since $p$ is simple in that case there are only two terms. One term for the edge of $p$ that comes into $v$ and one for the edge of $p$ that leaves $v$. The condition reduces to $c_f(p)=c_f(p)$. The property $c_f(p)>0$ is a consequence of $p$ consisting of finitely many edges, all of positive capacity and $c_f(p)$ being the minimum of those finitely many positive numbers.
– plop
Sep 4 '20 at 20:26
• @plop Make an answer? Sep 5 '20 at 6:02

Observe that if $$v$$ is not a vertex of $$p$$, then $$f_p(u,v)=0$$. When $$v$$ is in $$p$$ and not a source nor a sink, then there are only two vertices $$v_1$$ and $$v_2$$ such that the edges $$(v_1,v),(v,v_2)$$ are in $$p$$. Therefore, in the excess flow at $$v$$ $$\sum_u f_p(u,v)$$ only has two non-zero terms $$f_p(v_1,v)=c_f(p)$$ and $$f_p(v_2,v)=-f_p(v,v_2)=-c_f(p)$$.
To see that $$c_f(p)>0$$ just recall that it is defined as the minimum of the residual capacities of the edges of $$p$$. There are finitely many edges in $$p$$ and by definition of augmenting path the residual capacities of its edges are positive. So, you are taking the minimum of finitely many positive numbers. That results in a positive number.