I have the following problem:
Let $G=G_2(m,n)$ be a bipartite graph with vertex classes $V_1$ and $V_2$ containing a complete matching from $V_1$ to $V_2$. Prove that there is a vertex $x\in V_1$ such that for every edge $xy\in E_G$ there is a matching from $V_1$ to $V_2$ that contains $xy$.
I tried using Hall's theorem, but worked out nothing. Maybe it is the correct way to proceed, but do not know how.
Any hints?
How could the conclusion possibly fail? By Hall's theorem on the subgraph with the vertices $x,y$ removed, there would have to be a subset $U_1\subseteq V_1$ not containing $x$ such that $|\Gamma(U_1)\setminus \{y\}|<|U_1|.$ This means that in the original graph $G,$ the set $U_1$ is a non-empty proper subset of $V_1$ that is "critical" in the following sense.
A set $U_1\subseteq V_1$ is critical if $$|U_1|=|\Gamma(U_1)|$$ where $\Gamma(U_1)$ means the neighbours of $V_1,$ as a subset of $V_2.$
Critical sets are the structure that Hall's marriage theorem gives you. If there is a non-empty proper critical subset, use induction to reduce to the case where only $\emptyset$ and $V_1$ are critical. (Alternatively, consider a minimal critical set.)