Problem
COM-B2-M08-P008 Regular Bipartite Graph
#8
★★★☆☆ Level 3 of 5
Prove that every \(d\)-regular bipartite graph with \(d>0\) has a matching covering the whole left part.
Apply edge counting to arbitrary \(S\).
For any left-side set \(S\), exactly \(d|S|\) edges leave it. All enter \(N(S)\), and each vertex of \(N(S)\) has degree \(d\), so it receives at most \(d\) of these edges. Hence \(d|S|\le d|N(S)|\), so \(|N(S)|\ge |S|\). By Hall's theorem, the desired matching exists.
Key fact for decompositions of regular graphs.