Graph Theory37 sections · 1633 units
Open in Course

Maximum Matching

(Largest possible set)

A maximum matching is a matching with the largest possible number of edges. You cannot add any more pairs without breaking the matching constraint (two edges sharing a vertex). For example, if you have 55 people and 1010 schools, the maximum matching might pair all 55 people (size 55), or it might be smaller if some people have no valid school choices.

Finding this maximum is what Kuhn's algorithm does.