Prove that a $k$-regular bipartite graph has a perfect matching

Solution 1:

We want to use Hall’s theorem to guarantee a complete matching, and then show that the complete matching is actually a perfect matching. Let us first show the conditions for Hall’s theorem.

Since the graph is regular and edges go from $X$ to $Y$. Without loss of generality, consider $A \subseteq X$ to be an arbitrary subset, and denote by $N(A)$ the set of neighbors of elements of $A$.

Every edge with an endpoint in $A$ has an endpoint in $N(A)$, let $E_A$ and $E_{N(A)}$ denote the respective edge sets.

Then since $G$ is regular ($d$ is the degree of each vertex), $|E_A| = d |A|$ and $|E_{N(A)}| = d |N(A)|$, hence $ |A| \leq |{N(A)}|$. By Hall’s theorem there is a complete matching.

But $|X| = |Y|$, so every vertex in $Y$ is also matched to a vertex in $X$, which together match every vertex in the graph. Thus the complete matching is a perfect matching. $\blacksquare$

Solution 2:

As you have noted, there are $|S| \cdot k$ edges leaving $S$. Suppose the neighborhood set $N(S)$ of $S$ is smaller than $S$. Then there are $|N(S)| \cdot k < |S| \cdot k$ edges leaving $N(S)$, a contradiction.

Solution 3:

Let $S$ be any subset of vertices in the left vertex set of the $k$-regular bipartite graph. The number of edges adjacent to vertices in $S$ is exactly $|S|~ k$. Since the number of edges incident to each vertex in the right vertex set of the bipartite graph is exactly $k$, any set of $|S|~k$ edges in the bipartite graph will be incident to $|S|$ or more vertices in the right vertex set. (For example, fewer than $|S|$ vertices in the right vertex set can `accomodate' at most $(|S|-1)k$ edges.) Thus, the number of neighbors of $S$ is at least $|S|$. By Hall's theorem, the graph has a perfect matching.