Problem
COM-B2-M08-P019 Decomposition into Perfect Matchings
#19
★★★★★ Level 5 of 5
Prove that the edges of every \(d\)-regular bipartite graph can be decomposed into \(d\) perfect matchings.
Find one perfect matching and remove it.
A \(d\)-regular bipartite graph has a perfect matching. Remove its edges. Every vertex degree decreases by \(1\), so the remaining graph is \((d-1)\)-regular and bipartite.
Repeat the argument: find a perfect matching and remove it. After \(d\) steps all edges are removed, and the found matchings are pairwise disjoint and cover all edges.
A beautiful application of Hall with induction.