It is well known that for arbitrary flow networks, Goldberg's push-relabel algorithm takes $O(V^2E)$. Part of that comes from $O(V^2E)$ non-saturating pushes. Another part comes from $O(V)$ relabelling operations per vertex, each taking $O(V)$ time, for a total of $O(V^3)$ for all relabelling operations.
I'm interested in what happens to these bounds when we restrict edge capacities to be 1. It is clear that there are no more non-saturating pushes, so only saturating pushes, of which there are always $O(VE)$, remain.
However, I found a 1995 phd thesis by a student of Goldberg that claims (on p 13) that when edge capacities are 1 (and thus all pushes are saturating), the relabelling portion takes $O(VE)$ time instead of the usual $O(V^3)$.
How does this $O(VE)$ result follow?