constraint. The push operation can send flow from to if . This may add to and may delete from . The addition of to will not affect the valid labeling since . The deletion of from removes the corresponding constraint since the valid labeling property only applies to residual arcs in . If a preflow and a valid labeling for exists then there is no augmenting path from to in the residual graph . This can be proven by contradiction based on inequalities which arise in the labeling function when supposing that an augmenting path does exist. If the algorithm terminates, then all nodes in are not active. This means all have no excess flow, and with no excess the preflow obeys the flow conservation constraint and can be considered a normal flow. This flow is the maximum flow according to the max-flow min-cut theorem since there is no augmenting path from to . Therefore, the algorithm will return the maximum flow upon termination. Time complexity In order to bound the time complexity of the algorithm, we must analyze the number of push and relabel operations which occur within the main loop. The numbers of relabel, saturating push and nonsaturating push operations are analyzed separately. In the algorithm, the relabel operation can be performed at most times. This is because the labeling value for any node u can never decrease, and the maximum label value is at most for all nodes. This means the relabel operation could potentially be performed times for all nodes (i.e. ). This results in a bound of for the relabel operation. Each saturating push on an admissible arc removes the arc from . For the arc to be reinserted into for another saturating push, must first be relabeled, followed by a push on the arc , then must be relabeled. In the process, increases by at least two. Therefore, there are saturating pushes on , and the total number of saturating pushes is at most . This results in a time bound of for the saturating push operations. Bounding the number of nonsaturating pushes can be achieved via a potential argument. We use the potential function (i.e. is the sum of the labels of all active nodes). It is obvious that is initially and stays nonnegative throughout the execution of the algorithm. Both relabels and saturating pushes can increase . However, the value of must