Thesis Match bipartite matching via flows · ALG 14.3

Students (left) applied for thesis topics (right). Give as many students a topic as you can: a matching M, no student with two topics, no topic taken twice. Grow M by augmenting paths: click a free student, then a topic, and keep going until you reach a free topic. The right panel shows the same thing in the book's network: source z, sink s, all capacities 1, and M is a flow f with |f| = |M|. When no augmenting path is left, prove that M is maximum with a cut E(A, B) of capacity |M|. Click the last vertex of your path to take it back.