0
$\begingroup$

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

  • 0
    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.2012-10-16

1 Answers 1

1

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 does not belong to any perfect matching

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