# Complete matching in bipartite graph

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

• EDIT: By the Hall's theorem you have that, in $G$, $\lvert\Gamma(S)\lvert \geq \lvert S\lvert$, for all $S\in V_1$. So, when you remove $x,y$ from $G$, I do not see why $\lvert\Gamma(U_1)\setminus \{y\}\lvert < \lvert U_1\lvert$.
– plr
Commented Oct 23, 2017 at 14:24
• And where you put the definition of critical, where the neighbours are defined, wouldn't it be "$\Gamma(U_1)$ means the neighbours of $U_1$, as a subset of $V_2$"? Swapped $V_1$ for $U_1$.
– plr
Commented Oct 23, 2017 at 16:12
• @plr: The question to ask is: how can there fail to be a complete matching that includes $xy$? This is the same as asking: how can there fail to be a complete matching in the induced subgraph with the vertices $x,y$ removed? You can apply Hall's theorem to that subgraph. And yes you're right about the definition of the neighbor set.
– Dap
Commented Oct 23, 2017 at 17:33