I have difficulty understanding the following lemma from CLRS:
Let G be a flow network, s and t be source and sink nodes, f be a preflow from s to t, and h be a height function on G. Then there is no augmenting path from s to t in the residual graph Gf.
Why is this?
The following is a paraphrased and expanded version of the proof in CLRS, Second Edition.
The intuition behind the proof is that if h is a height function, then we must have that in any path from s to t, the height of the nodes along the path can decrease by at most one in each step (since height functions satisfy the property that h(u) ≤ h(v) + 1, meaning that h(v) ≥ h(u) - 1). So now suppose that you have an augmenting path in the residual graph that goes from s to t. In that case, if there's an augmenting path, there must be an augmenting simple path from s to t, so we don't need to worry about cycles.
So let's think about what this simple path must look like. If there are |V| vertices in the graph, our simple path must have at most |V| vertices in it, which means that it has at most |V| - 1 edges in it. Because there are at most |V| - 1 edges, and the height of each node can drop by at most one per step, the maximum possible decrease in height from the starting node s is |V| - 1. Now, we know that h is a height function, which means that h(s) = |V| and h(t) = 0. But now we have a contradiction - since we start at height |V| and decrease the height by at most |V| - 1, the height at the end of the path has to be at least 1, and since h(t) = 0 we know that this path can't actually end at t. This contradiction guarantees that our assumption was wrong and that there really is no augmenting path from s to t.
Hope this helps!