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)| \geq |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)| \geq |S|$, but I don't why should we do this. If anyone could help me with some tipps, I would be very grateful.
Best Answer
Let the two parts of the graph be $X$ and $Y$, and suppose WLOG $|X|\geq |Y|$. Let $S\subset 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))\geq D(S)=n|S|\Longrightarrow |N(S)|\geq |S|. $$ 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)\subset Y$ and $|X|\geq |Y|$. Hence, this matching is a perfect matching.
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.