1
$\begingroup$

I have a problem here and would appreciate your help.

I have a bipartite graph $G = (A \cup B,E)$ which has a matching $M$ of size $|A|$. We need to prove there's a vertex in $A$ such that each edge that contains this vertex belongs to some matching of size $|A|$.

We tried using induction; we also tried using Hall's theorem and separating two cases (when $|N(X)|>|X|$ for some subset $X$ of $A$, or $|N(X)|=|X|$) but got stuck.

Any ideas?

$\endgroup$
3
$\begingroup$

Assume the contrapositive, i.e. every vertex $v$ has an edge $e_v$ that does not belong to any matching of size $|A|$.

Let $v_1$ be a vertex of $A$, $w_1$ the vertex of $B$ that is the other endpoint of $e_{v_1}$. $w_1$ must be saturated by $M$, or we can exchange the edge of $M$ that saturates $v_1$ by $v_1w_1$ to get a matching of size $|A|$ that contains $e_{v_1}$. Now let $v_2$ be the vertex of $A$ that is the other endpoint of the edge of $M$ that saturates $w_1$. Let $w_2$ be the endpoint of $e_{v_2}$ etc.

We get a path that starts at $v_1$, alternates between edges that are in no matching of size $\left|A\right|$ and edges of $M$. Such a path must close eventually.

On the resulting cycle swap both types of edges and you get a matching of size $\left|A\right|$ containing several of the $e_v$ edges. Contradiction.

$\endgroup$
  • $\begingroup$ nicely done! thanks! $\endgroup$ – idan hav Feb 10 '14 at 15:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.