Respecting endpoints on both sides
A bipartite graph separates vertices into two sets, with edges crossing between them. Edges might represent worker–task compatibility. A matching selects edges with no shared endpoints, and maximum-cardinality matching seeks as many pairs as possible.
A perfect matching covers every vertex, which a maximum matching need not do. Group sizes and compatibility structure can limit coverage. Maximizing total reward instead of pair count introduces weights and a different optimization objective.
References: [1]
Rearranging pairs along augmenting paths
Greedily taking a free edge can stop short of an optimum. If A can pair with X or Y while B can only pair with X, choosing A–X blocks a direct addition, but rearranging to A–Y and B–X gives two pairs.
An augmenting path alternates unmatched and matched edges and begins and ends at unmatched vertices. Flipping all its memberships adds one net edge while preserving a valid matching, allowing reassignment rather than only irreversible additions.
References: [2]
Connections to flow and vertex cover
A flow reduction adds a source and sink with unit capacities into left vertices and out of right vertices. Integral unit flow corresponds to pairs. Princeton’s reduction gives compatibility edges infinite capacity; the unit endpoint capacities still enforce matching constraints.
Kőnig’s theorem equates maximum matching size with minimum vertex-cover size in bipartite graphs, where a cover touches every edge. This provides an additional optimality certificate, but the equality should not be generalized to arbitrary nonbipartite graphs.