CLRS - Maxflow Augmented Flow Lemma 26.1 - don't understand use of def. in proof

Question

In Cormen et. al., Introduction to Algorithms (3rd ed.), I don't get a line in the proof of Lemma 26.1 which states that the augmented flow $f\uparrow f'$ is a flow in $G$ and is s.t. $|f\uparrow f'| =|f|+|f'|$ (this is pp. 717-718).

My confusion: When arguing flow-conservation they use the definition of $f\uparrow f'$ in the first line to say that for each $u\in V\setminus\{s,t\}$

$$ \sum_{v\in V} (f\uparrow f')(u,v) = \sum_{v\in V} (f(u,v)+f'(u,v) - f'(v,u)), $$

where the augmented path is defined as

$$ (f\uparrow f')(u,v) = \begin{cases} f(u,v)+f'(u,v) - f'(v,u) & \text{if $(u,v)\in E$}, \\ 0 & \text{otherwise}. \end{cases} $$

Why can they ignore the 'otherwise' clause in the summation? I don't think the first clause evaluates to zero in all such cases. Do they use flow-conservation of $f$ and $f'$ in some way?

Answer 1

Note: The notations and definitions used below are borrowed from the third edition of the book.

To answer this question, first, observe that if $(u,v) \notin E$, then by flow definition,

$$f(u,v) = f'(u,v) = (f \uparrow f')(u,v) = 0 \, .$$

Furthermore, since $f'(v,u) \le c_f(u,v) = f(u,v)$, it is obtained that $f'(v,u) = 0$. This simply implies that $\forall (u,v) \notin E$,

$$(f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) = 0 \, .$$

Therefore, the definition of augmented flow can be generalized for all $(u,v) \in V \times V$ to be as follows:

$$ (f \uparrow f')(u,v) = f(u,v) + f'(u,v) - f'(v,u) \, .$$

The rest of the proof follows from this observation which, of course, is not explicitly explained in the text.

P.S. Please note that the formal definition of flow in the third edition of the book is significantly different from that in the second edition. In particular, in the second edition, there is a flow property named skew symmetry that requires $f(u,v) = - f(v,u), \forall u,v \in V$. This property has been removed in the third edition due to the assumptions that $(v,u) \notin E$ if $(u,v) \in E$ and $f(v,u) = 0$ if $(v,u) \notin E$. Because of this, the definitions of flow conservation in two editions are also different. Lots of such confusions, in fact, come from this change of definition that is presumably intended to simplify the proofs, but turned out being more perplexing. I personally would rather to stick to the second edition of the book for this particular chapter.

Answer 2

There is an errata in this printing, the corrected proof is found in the link below. Indeed, the correction requires you to consider subsets $V_1=\{v:(u,v)\in E\}$ and $V_2=\{v:(v,u)\in E\}$.

https://www.cs.dartmouth.edu/~thc/clrs-bugs/pages/pp-718-720.pdf