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.
Articles by others on the same topic
There are currently no matching articles.