Problem
COM-B2-M08-P015 Perfect Matching in a Regular Graph
#15
★★★★☆ Level 4 of 5
Prove that every \(d\)-regular bipartite graph with \(d>0\) has a perfect matching.
First prove the parts are equal, then apply Hall.
Let the parts be \(A\) and \(B\). Counting edges by parts gives \(d|A|=d|B|\), hence \(|A|=|B|\).
By the regular bipartite graph argument, there is a matching covering \(A\). Since the parts are equal, it also covers \(B\). Therefore the matching is perfect.
A very important result for olympiad graph problems.