Proof of Max-flow Min-cut

Construct the following cut: Let the top nodes be the unmatched left nodes along with all those nodes reachable by alternating white-blue paths from them. Let the bottom nodes be the others.

Facts:

• All y top right nodes are matched. What would it mean if a top right node were unmatched?

• All x bottom left nodes are matched. By definition... all unmatched left nodes were put on top.
• There are z=0 edges from top left to bottom right. This is because there can be no such edge. Why? Such an edge couldn't be white, because any right node with a white edge from the top is itself a top, by definition. But, such an edge couldn't be blue, either, because all top left nodes are either unmatched (the starter nodes), or matched to a top right node (the others).

So, the size of this cut is equal to the size of the matching. Therefore, we have a maximum matching, since cut sizes are upper bounds on matching sizes.