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

Question

Prove that a $k$-regular bipartite graph has a perfect matching by using Hall's theorem.

Let $S$ be any subset of the left side of the graph. The only thing I know is the number of things leaving the subset is $|S|\times k$.

Answer 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$