Proof of lemma for flow in residual graph

Question

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$?

Answer 1

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)$.

So, the excess flow is zero.

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.