Knowing that $G$ is a Bipartite Graph $g=(S,T,E)$ and $G − {x, y}$ has a perfect matching* $\forall x\in S, \forall y\in T$, how can I demonstrate that a perfect matching for $G$ exist?
*A perfect matching is a matching which saturates all the vertices in $G$.
Best Answer
Take any edge $xy$ in $G$.
By supposition $G-\{x,y\}$ has a perfect matching $M$.
Therefore, $M \cup \{xy\}$ is a perfect matching for $G$.