A perfect matching pairs every vertex in the smaller set. If and , a perfect matching would pair all left vertices.
Perfect matching exists if and only if max matching size equals . If matching size is smaller, some vertices remain unmatched.
Hall's theorem gives a condition: perfect matching exists iff for every subset of , the neighborhood has at least vertices. This is useful for proving existence without computing the matching.