k-regular bipartite graph
Task number: 3999
Prove that the set of edges of a \( k \)-regular bipartite graph can be expressed as the union of \( k \) perfect matchings.
Hint
Prove by induction and use the Hall theorem.
Solution
If \( A, B \) are the classes of bipartition of the bipartite graph, then for each \( I \subseteq A \) it holds that \( I \) is incident with \( k | I | \) edges. If \( Y = N (I) \) contain less than \( | I | \) vertices, then with \( Y \) could be incident less than \( k | I | \) edges, which is not possible.
The Hall condition is met and therefore there is a perfect matching \( P \) in the graph, i.e. one that contains all vertices of the graph. By removing the edges of this matching, we get a \( (k-1) \)-regular bipartite graph.
If, according to the induction, the edges of this reduced graph are decomposable to a collection of perfect matching, by adding \( P \) to the decomposition we obtain a decomposition of the original graph.
