Graph Theory37 sections · 1633 units
Open in Course

Reduction to Max Flow

(Flow network construction)

You can solve bipartite matching using max flow. Create a source ss connected to all vertices in LL with capacity 11. Connect all vertices in RR to a sink tt with capacity 11. Use the original edges with capacity 11.

The max flow from ss to tt equals the maximum matching size. Each unit of flow corresponds to one matched pair. This works because capacities force each vertex to participate in at most one edge.