Let $G$ be bipartite such that $G=(Y,E)$. Let $W \subset Y$ be a minimum vertex cover in $G$ and let $M \subset E$ be a maximum matching in bipartite graph $G$. Prove that for any edge $wy \in E$, if both $w, y \in W$, then $wy$ is not an element of the matching $M$.
I tried showing that if $wy$ is not an element of the matching of $M$, then it should be an augmenting path in $M$ given $M$ is a maximum matching. However, I got stuck in showing that $wy$ would form an augmenting path in $M$. Can anyone help or guide me?
Here is an argument. This involves some case analysis though. We know that $M$ is a maximum matching, and $W$ is a minimum vertex cover in $G$. Now consider $x,y \in W$, and suppose $xy \in M$.
Let us separate the vertices of $G$ into two sets, $V_1:=\{\text{vertices in min vertex cover}\}$, and $V_1^c:=\{\text{vertices NOT in min vertex cover}\}$. Remember that for all matchings, at least one endpoint must be in $V_1$.
By the definition of min vertex cover, $x,y \in W$, implies that removing either one or both of $x$ and $y$ from $W$ leaves some edges uncovered. Let us call these edges as $xv_1,yv_2, v_1, v_2 \in V_1^c$.
Why is that so? Suppose $xv_1$ exists, however there are no edges that are left uncovered if we remove $y$ from $W$. Well, then $W$ is not the minimum vertex cover, since removing a vertex from $W$ results in a vertex cover with 1 fewer vertex. The same argument for the symmetric case.
Suppose both $xv_1,yv_2$ doesn't exist. Again, we can remove either $x$ or $y$ (but not both, since there is an edge $xy$) from $W$.
Now, we have $xv_1,yv_2,xy$. Instead of having $xy \in M$, why not $xv_1,yv_2$ in $M$ instead? We would have a larger size matching! But, we must ask why are $xv_1,yv_2$ valid matchings.
Consider $xv_1$, and suppose it is not a valid matching. Then, $v_1$ must be part of another matching, say $v_1k_1$. But that is impossible! If $v_1k_1$ is a matching, since $v_1 \in V_1^c$, then $k_1 \in V_1$. But we have just argued that $v_1$ is uncovered if we remove $x$ from $W$. So we arrive at a contradiction, and there doesn't exist such a matching $v_1k_1 \in M$. The same argument applies for $yv_2$.
Now we can conclude, if $x,y \in W$, and $xy \in M$ is a matching, then either $W$ is not a min vertex cover or $M$ is not a max matching.
Also, if you really want to use an argument with alternating paths, consider the path $v_1 \rightarrow x \rightarrow y \rightarrow v_2$. That is an augmenting alternating path. I'm a bit fuzzy on how to use augmenting alternating paths exactly, but you should be able to carry it over the finish line with that.