7
$\begingroup$

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?

$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ 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$. $\endgroup$
    – plr
    Commented Oct 23, 2017 at 14:24
  • $\begingroup$ 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$. $\endgroup$
    – plr
    Commented Oct 23, 2017 at 16:12
  • $\begingroup$ @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. $\endgroup$
    – Dap
    Commented Oct 23, 2017 at 17:33

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .