# why does relabel take O(VE) time total for unit capacity flow networks?

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?

The $$O(VE)$$ result actually holds in general, not just for unit edge capacity, hence it has nothing to do with edge capacity being 1.
This result is proven in Exercise 26.4-3 of CLRS, and thus the $$O(V^3)$$ quoted in the question is not tight.