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
    Are you familiar with Hall's theorem? One way to do this is to carefully examine its proof.2012-10-16
  • 0
    I just learnt Hall's theorem. Can you give some hints on this?2012-10-16
  • 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