Proof for Shortest augmenting path. Let f be augmented into g.
Let d_f(v)>d_g(v) be the contradiction we wish to refute.

We assume that the v was the first vertex that whose shortest distance was reduced by augmentation. By first vertex i mean first along that path, not the first augmentation in the algorithm itself. This is by the assumption for above contradiction.----------------1

Let there be an edge (u,v) that was on the augmented path g. (u,v) in E_g. Where E_g is the edge set of path g.
d_g(u)=d_g(v)-1 ------- 2
Because the path to v must cross through u.
d_g(u)>=d_f(u) ------- 3
Because if d_g(u)<d_f(u) then the distance to u could have been the first on the path g that was reduced violating Assumption 1. So u should have been atleast as much as it was before...


If we can somehow prove that (u,v) was not in E_f... Then we can say that there was no predecessor of v that could have been chosen such that we had a path to augment in the first place. And therefore no such path can exist. This is a sufficient thing to do to prove our point.

(You may argue that (u,v) can only come on g after the augmentation. That is possible if u was a bottleneck earlier and was reversed to reach v. That is ok, what I am just saying here is that no such edge (u,v) existed earlier. )

Now Let E_f be the edge set of path f. Let (u,v) be an edge in E_f (We will refute this in a while).
Now Using this I can say:
d_f(v)<=d_f(u)+1. Otherwise u is not parent of v and there are more edges between u and v... So Just pick a u that is parent..Doesnt matter which...
=> d_f(v)<=d_f(u)+1<=d_g(u)+1 --- By 3 above
=> d_f(v)<=d_f(u)+1<=d_g(u)+1 =d_g(v) -- Equality because u->v is an edge on g....
=> d_f(v)<=d_g(v)
Which is Contradiction, so no such (u,v) exists in E_f such that we could get an augmenting path g...