If G is n regular, then G has n disjoint perfect matchings. Let G be a bipartite simple graph show

excluderho

excluderho

Answered question

2022-06-22

If G is n regular, then G has n disjoint perfect matchings.
Let G be a bipartite simple graph show that:
If G is n regular, then G has n paarwise disjoint perfect matchings.
It's firstly easy to show that G has a perfect matching by using Hall’s Theorem, | N ( S ) | | S | with N the potential mathings and S a arbitary subset of one part of the bipartite graph G. But how to show that there is n perfect matchings and besides disjoint. I've seen a answer by multiplying d to | N ( S ) | | S | , but I don't why should we do this. If anyone could help me with some tipps, I would be very grateful.

Answer & Explanation

Nola Rivera

Nola Rivera

Beginner2022-06-23Added 21 answers

Step 1
Let the two parts of the graph be X and Y, and suppose WLOG | X | | Y | . Let S X be an arbitrary subset of X. Let D(U) be the sum of the degrees of any collection of vertices U. Now n | N ( S ) | = D ( N ( S ) ) D ( S ) = n | S | | N ( S ) | | S | ..
Step 2
So by Hall's Theorem, there exists a matching that pairs off all vertices in X. This must then necessarily pair off all vertices in Y since N ( X ) Y and | X | | Y | . Hence, this matching is a perfect matching.
Step 3
Now delete all edges in this perfect matching; we will be left with a ( n 1 )- regular bipartite graph. Repeating the process above another n 1 times then gives the required n disjoint perfect matchings.

Do you have a similar question?

Recalculate according to your conditions!

New Questions in Discrete math

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?