Let $G$ be a $k$-regular bipartite graph, $k \ge 2$. Prove that every edge of $G$ appears in some perfect matcing in $G$. Is this proof correct?

Question

Using Hall's Theorem, there could only be a perfect matching when the set of $|A|$ vertices have the same number of vertices as set $|B|$, and that there is a subset of vertices $|U|$ in $A$ that is $\le$ the subsets of vertices of B that are connected to vertex $|U|$ (which I'll denote as $|N(U)|$. so I believe I have to show that. What I did was let $E'$ be the set of edges connected to $U$ and $N(U)$. Since it's a k-regular bipartite, $|E'| \le k *|N(U)|$. Therefore, $|N(U) \ge|U|$.Now to prove $|A| =|B|$, let $U = A$, which means $|N(A| \ge |A|$ and since $|N(A) \ge B$, $|B| \ge |A|$. Using the same argument for $B$, I conclude $|A|=|B|$. Is this correct?

Answer 1

Here's an alternative approach:

Pick any perfect matching, one exists by Hall's. If your edge is in it great. If not throw away those edges, you are now left with a (k-1)-regular bipartite graph. Rinse and repeat.