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.

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email