Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
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
add comment

1 Answer

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.