Perfect matching criterion for a regular pair with minimum degree

ID: perfect-matching-criterion-for-a-regular-pair-with-minimum-degree

Let be a regular pair of vertex sets with parameter , equal class sizes , density greater than , and every vertex having at least neighbors across the pair. Then it has a perfect matching. To prove Hall's condition, take . If , one vertex already supplies at least neighbors. If and , the two large sets and have density zero, contradicting regularity and the positive density surplus. Finally, if , every vertex of has a neighbor in , so . The empty subset satisfies Hall's condition directly.

New to topics? Read the docs here!