All stable matchings of a given bipartite graph cover the same vertices.

920 Views Asked by At

I believe this proof is pretty obvious, since stable matchings saturate all of the vertices, right?

Still I will give it a go: Let $M_1$ and $M_2$ be two matchings such that they don't cover the same vertices. So there exists some vertex, say $m$ that is cover by $M_1$ and not by $M_2$. Let $mn$ be an edge in $M_1$. Now $M_2$ must cover $n$ with an edge, say $kn$, or otherwise in $M_2$ we have two vertices that are not covered. I am stuck here and I don't know how to reach a contradiction. Is this the right approach?

1

There are 1 best solutions below

1
On

Actually, a stable matching does not necessarily saturate all the vertices. In case where preference lists are not complete, it is possible that someone is unmatched in stable matchings.

To prove this statement, you should use the stability condition. Let $M_1$ and $M_2$ be two stable matchings. Want to show $M_1$ and $M_2$ cover the same vertices. Assume not and assume $a_1b_1\in M_1$ but $a_1$ is not matched in $M_2$. Then, to avoid $a_1b_1$ being a blocking pair of $M_2$, $b_1$ must prefer her matching in $M_2$ to her matching in $M_1$, for which we write $M_2(b_1) >_{b_1} M_1(b_1)$. Let $a_2 = M_2(b_1)$, then $a_2\neq \emptyset$. With similar reasoning, to avoid $a_2b_1$ blocking $M_1$, we must have $M_1(a_2) >_{a_2} b_1$, and $b_2:=M_1(a_2) \neq \emptyset$. We may continue the process and define $a_3, b_3, a_4, \cdots$. All these are guaranteed to be non-empty by the arguments (stability) aforementioned. However, the graph is finite, so we must visit $a_1$ again, which is a contradiction.