It is lemma 4.3, I have been thinking about it for 3 days. A detailed description is given below.
In "A new approach to the Maximum-Flow Problem", 1988, by Goldberg, to prove the $\mathcal{O}(n^3)$ bound, the author breaks the whole execution into numerous "pass", a pass is just like a run in the BFS-style traversal of executing push/relabel on the vertices activated previously. He tries to show that there exists a $\mathcal{O}(n^2)$ upper bound for the number of passes, and in each pass, the number of non-saturating pushes must be lower than $n$.
The latter statement is trivial, however, the former one is hard for me to show.
He established a measure $\Phi$, the maximum of the label of all active vertices. And it might go up, go down or remain constant in a pass. When it goes up or remains constant, there must be an increase in the sum of labels over all vertices, which has a upper-bound $2n^2$. So the total number of passes that make it go up or remain unchanged is $2n^2$.
Considering that $\Phi$ is equal (both be 0) after the algorithm terminates (where there are no active vertices) and before the first pass(when using simple initialization), the number of passes that decrease the $\Phi$ is smaller than the upper bound of the number of passes that increase $\Phi$. So here another upper bound of $2n^2$ can be drawn. (I think here might be problematic, $\Phi$ can follow a pattern like $1, n^2, n^2 - 1, n^2 - 2, ...., 1, n^2$, here the number of increasing path is at a magtitude $n^2$ lower than that of decreasing pass. Though clearly it is impossible, but proving that need other information on the pattern of the move of $\Phi$. )
In total, the number of passes has an upper bound $4n^2$.
I could not think of why there must be one label increased (equivalently, a relabel operation triggered) if $\Phi$ stays the same.
The proof above is slightly modified to make it easier to follow, but the key statement, as in original text, 'If $\Phi$ is not changed by the pass, some vertex label must increase by at least 1' is still mysterious for me.
It must be true that the number of passes cannot be larger than $4n^2$, but how to prove it.
The paper is now open access, here is the link: goldberg
We have to look more closely at the increases in $\Phi$ beyond just saying "each pass which increases $\Phi$ increases a label, and there can be at most $2n^2$ increases in labels". The actual fact we use is that the maximum value of a label is less than $2n$, so the sum of the labels can only ever increase by at most $2n^2$.
If $\Phi$ increases by $k$ during a pass, then some label increases by at least $k$; therefore the sum of the increases in $\Phi$ is at most $2n^2$. This could hypothetically mean $2n^2$ passes in which $\Phi$ increases by $1$, or $2n$ passes in which $\Phi$ increases by $n$; it cannot mean $2n^2$ passes in which $\Phi$ increases by $n$.
The sum of the decreases in $\Phi$ is equal to the sum of the increases, since $\Phi$ starts and ends at $0$, so the sum of the decreases is also at most $2n^2$. Therefore there can be at most $2n^2$ passes which decrease $\Phi$.
(Another thing to point out is a hidden argument in the claim "If $\Phi$ increases by $k$ during a pass, then some label increases by at least $k$". We must argue that $\Phi$ never increases due to making an inactive vertex with a very high label active. Indeed, we only make a vertex active by pushing flow to it from an active vertex with higher label; therefore the only way that the highest label of an active vertex can change is when an already-active vertex increases in label.)
This does not yet address the number of passes where $\Phi$ stays the same. The easiest thing to do is to prove that there are at most $2n^2$ of these.
The statement that takes some thinking about from the paper is
If no distance label changes during the pass, then two things must be true:
As a result, at the end of the pass, there are no longer any active vertices with label $\Phi$, so $\Phi$ decreases.
The next statement
is just the contrapositive of the previous statement. We use it to conclude that because there are at most $2n^2$ increases in labels, there are at most $2n^2$ passes where $\Phi$ is inchanged.
Combining the two arguments above carelessly only says that there are at most $6n^2$ passes. If we want to get to $4n^2$, argue as follows.
Let there be $k$ passes where $\Phi$ is unchanged. Then there are $k$ increases in labels during those passes, so the sum of labels can increase by at most $2n^2-k$ during other passes. So the sum of increases in $\Phi$, and therefore also the sum of decreases in $\Phi$, are at most $2n^2-k$ each. This means that there are at most $2n^2-k$ passes where $\Phi$ increases and at most $2n^2-k$ passes where $\Phi$ decreases. In total, there are $k + (2n^2-k) + (2n^2-k) = 4n^2 - k \le 4n^2$ passes.