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