During the algorithm we maintain a potential formula_14 and an orientation of formula_19 (denoted by formula_24) which has the property that the edges oriented from formula_9 to formula_7 form a matching formula_27. Initially, formula_14 is 0 everywhere, and all edges are oriented from formula_7 to formula_9 (so formula_27 is empty). In each step, either we modify formula_14 so that its value increases, or modify the orientation to obtain a matching with more edges. We maintain the invariant that all the edges of formula_27 are tight. We are done if formula_27 is a perfect matching.