
in the second part when talking about the graduation problem it says
It is important to understand that any order to iterate through set A can be considered when solving the standard bipartitematching problem. For example, it doesn't matter what element from set A we choose to be the first one to be matched. Consider the solution found by the algorithm containing this element x from A, matched with an element y from B. Also, we should consider any optimal solution. Clearly, in the optimal, y must be matched with an element z from A, otherwise we can add the pair xy to the matching, contradicting the fact that the solution is optimal. Then, we can just exchange z with x to come with a solution of the same cardinality, which completes the proof.
Let A have one element a. Let B have 2 elements b, c. Let there be the paths a>b and a>c. there are 2 maximal matchings a>b and a>c. pick one of them say a>b. x=a y=b. now in the other optimal solution a>c b is not matched but according to the proof it must be. am i missing something? 