Prove that a $k$-regular bipartite graph has a perfect matching 
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$. 
 A: 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.
A: 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$
A: 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.
