Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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?
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.
