Push-relabel algorithm: what is the definition of the height function? Suppose we are able to discharge the excess from every vertex and continue to have a valid height function. Why must the flow be maximum? Suppose we have not discharged the excess from vertex u. Why must there exist a path from u to s in the augmenting graph? What is the max height of u? Why? What is the max number of times a single vertex can be relabeled?