# Can Hall's Marriage Theorem be reduced to the $d$-regular case?

The version of Hall's Marriage Theorem I'd like to consider is the following:

Theorem Let $$G$$ be a finite bipartite graph with bipartition $$\{X,Y\}$$ and edge set $$E$$, so that we can view $$E$$ as a relation from $$X$$ to $$Y$$. Suppose that, for all $$S \subseteq X$$, $$\lvert \{y \in Y : \exists x \in S (xEy)\} \rvert \geq \lvert S \rvert.$$ Then there exists a subset $$E' \subseteq E$$ which is an injection $$X \to Y$$.

There are many interesting proofs of this theorem. A special case is when $$G$$ is regular; in this case, we must have $$\lvert X \rvert = \lvert Y \rvert$$ and also the inequality is automatically satisfied. To spell it out, this special case of the Hall Marriage Theorem is:

Corollary Let $$G$$ be a finite $$d$$-regular bipartite graph with bipartition $$\{X,Y\}$$ and edge set $$E$$, so that we can view $$E$$ as a relation from $$X$$ to $$Y$$. If $$d>0$$, then there exists a subset $$E' \subseteq E$$ which is a bijection $$X \to Y$$.

This special case is somewhat easier to prove – for example, it admits a slick proof by applying the Krein-Milman Theorem to the space of "fractional perfect matchings". My question is:

Is there an easy way to reduce Hall's Marriage Theorem to this corollary?

In other words, if we have already proven the corollary, is there a relatively short proof of the theorem itself? Or, perhaps: is there a slightly more general statement we can prove for regular bipartite graphs which implies the marriage theorem for arbitrary bipartite graphs?

A naive thought is that a reduction should look like: start with $$G$$ not assumed regular, then add vertices and edges to make it regular, but somehow ensure that the resulting bijection produced by the corollary restricts to an injection on the original graph.

I've tried to come up with an argument myself but got ~nowhere, so I'd appreciate hearing any ideas you have.

• Do you know that the Hall's Marriage theorem always applies for regular graphs, so that every bipartite regular graph has a perfect matching? I don't see how your reduction will go since I don't see which regular graphs you will associate with bipartite graphs without a perfect matching. Commented Mar 4 at 8:22
• Yeah that's fair! I'm not sure either. Commented Mar 4 at 18:18
• A maybe-plausible reduction is to prove Konig's theorem using the $d$-regular case of Hall. Here, given a minimum vertex cover $U$ of $G$, we want to prove that there is a matching which saturates $U$. If we could find a $d$-regular subgraph of $G$ which contains $U$ (but may be missing some other vertices), that would do it. Certainly this is possible to find - in particular, the matching that saturates $U$ is a $1$-regular subgraph of $G$ that does the trick. The question is whether it is possible to find without already knowing that the matching exists. Commented Mar 4 at 19:06