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

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.

Answer 2

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 $k$-regular ($k$ is the degree of each vertex), $|E_A| = k |A|$ and $|E_{N(A)}| = k |N(A)|$. But $E_A \subseteq E_{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$

---

Remark: This answer originally used the letter $d$ for what the author of the question denoted $k$. Thus the comments use these interchangeably.

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

Answer 4

Note that for $k=1$ what you have is precisely a perfect matching (, proving that $|A|=|B|$). And note that the number of edges in a k-regular graph is $k|V|/2$ and for $k+1: (k+1)|V|/2$ meaning that we are adding $|V|/2$ edges. Now suppose $k=2$ or inductively $n+1$ (note that $|V|/2 = |A| = |B| > n $ since every vertex of $A$ is connected to n+1 vertices of $B$ and vice versa), if we are not adding these edges in the form of a perfect matching then two edges will share a vertex and one vertex will have degree $3$ (or $n+2$) and the graph in contrary to assumption will not be $2$ or $n+1$ regular. thus since all edges added are distinct, we end up with $2$ or $n+1$ distinct matchings.