0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

Let $x \in S$ and $y \in T$, then by the Hypothesis there is a perfect matching $M$ on $G-x,y$. Let $x*\in S-x$ and $y*\in T-y$ be two vertices connected by an edge in $M$. Then by the Hypothesis, there is a perfect Matching $M*$on $G-x*,y*$. The edge set formed by taking $M*$ and adding the edge connecting $x*$ to $y*$ in $M$ is a perfect matching for G.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

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.