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$.
Let $G$ be a bipartite graph with bipartition $X$ and $Y$ having a matching from $X$ into $Y$.
-
0I 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. – 2012-10-16
1 Answers
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).