# Let $G$ be a bipartite graph with bipartition $X$ and $Y$ having a matching from $X$ into $Y$.

Prove that there is a vertex $x\in X$ such that every edge incident with $x$ is contained in some matching from $X$ into $Y$.

-
Are you familiar with Hall's theorem? One way to do this is to carefully examine its proof. – Chris Eagle Oct 16 '12 at 17:09
I just learnt Hall's theorem. Can you give some hints on this? – Chuwei Zhang Oct 16 '12 at 17:15
I see. I need to show a subset on which Hall's condition critically holds. And use induction, like in the proof for Hall's theorem. – Chuwei Zhang Oct 16 '12 at 22:38

Presumably:

• A matching in this context means perfect matching (also known as a 1-factor), otherwise the claim is trivially true without the conditions placed on the graph (the individual edges themselves form a matching).

• A bipartite graph should say a regular bipartite graph, otherwise the claim is false. Counterexample:

The orange edge in the above bipartite graph does not belong to any perfect matching, despite the graph itself having a perfect matching.

If the above bullet points are correct, then Hall's Marriage Theorem can be used to prove the existence of a 1-factorisation (and thus every edge belongs to a perfect matching).

A sketch of the required steps:

• For vertices $v \in X$, defined $S_v$ to be the set of neighbours of $v$. Hence we have a family of sets $\mathcal{S}=\{S_v\}_{v \in X}$.
• Show that, for any $W \subseteq \mathcal{S}$, the marriage condition is satisfied for $W$, that is, $$|W| \leq \left| \bigcup_{A \in W} A \right|.$$
• Conclude that the graph has a perfect matching, and thus, by induction, contains a 1-factorisation.

In this answer, I explain how to use Hall's Marriage Theorem in the context of $(0,1)$-matrices (which are equivalent to bipartite graphs via their biadjacency matrix; see Wikipedia).

-