[Math] $G$ has a perfect matching if $G$ is bipartite and all vertices have the same degree

Question

The Question:

Show that if $G$ is bipartite and that all of its vertices have the same degree, then $G$ has a perfect matching.

---

My Thoughts:

I have tried using Induction on the common degree of the vertices, but it doesn't seem to work as we do not know how many vertices (or edges) there are.

I can see that this is trivially true for when the common degree is $1$ (in which case the perfect matching is simply $M=E(G)$. It is also true when the common degree is $2$, since $G$ would just be a collection of even cycles.

But in general I don't see how to use the fact that all vertices have the same degree. Any hints?

Answer 1

For each subset $U$ of the vertices of $G$, let us write the set of vertices $v$ adjacent in $G$ to at least one vertex of $U$ as $N_G(U)$.

Hall's Theorem: Let $G$ be a bipartite $d$-regular graph with parts $S$ and $T$. Then $G$ has a perfect matching if both (i) every subset $U$ of $S$ satisfies $|N_G(U)| \geq U$ and (ii) every subset $V$ of $T$ satisfies $|N_G(V)| \geq |V|$. [Implicit in this is that $|S|$ must equal $|T|$].

Let $U$ be a subset of $S$. For each vertex $v$ in $T$ let $d_S(v)$ be the number of neighbors in $S$ that $v$ has in $G$. Then on the one hand, $\sum_{v \in N_G(U)} d_S(v) =d|S|$ (because every vertex in $G$ has the same degree $d$), but on the other hand, $d_S(v) \leq d$ (because every vertex in $G$ has the same degree $d$ so $d$ is an upper bound for $d_S(v)$). Conclude that the only way both of the above could hold is if $N_G(S)$ is at least as large as $S$.

Repeat the above line of reasoning for any subset of $T$. And then finish using Hall's.