Two groups — workers and jobs, students and schools — with lines showing who’s compatible. Pair them one-to-one so you match as MANY as possible. The trick: if you find a match, look for an ‘augmenting path’ that re-shuffles existing pairs to free up room for one more. Repeat until you can’t — that’s guaranteed maximum. It assigns residents to hospitals and ads to slots. Slide to add matches one augmenting path at a time.
In a bipartite graph (two disjoint vertex sets, edges only across), a MATCHING is a set of edges with no shared endpoints; maximum matching pairs as many as possible. The augmenting-path method: an alternating path that starts and ends on unmatched vertices can be FLIPPED to increase the matching by one; repeat until none exists (Berge’s theorem: a matching is maximum iff no augmenting path). Hopcroft–Karp does it in O(E√V). König’s theorem ties it to vertex cover (max matching = min cover in bipartite graphs), and it generalizes to weighted assignment (Hungarian algorithm). It solves job/task assignment, scheduling, and resident-hospital matching. A fail-loud self-check throws unless it finds the known maximum matching. ◆ real graph algorithms, node-verified.
Shown unweighted on a bipartite graph; WEIGHTED assignment needs the Hungarian algorithm, and general (non-bipartite) matching needs Edmonds’ blossom algorithm. The augmenting-path maximality (Berge) is exact.