# Proving that this matching is stable

Consider the stable marriage problem with $$n$$ men and $$n$$ women. Let $$A$$ and $$B$$ be two stable matchings, and suppose that we form a new matching $$C$$ by assigning to each men his favorite partner between the ones he gets in $$A$$ and $$B$$. Prove that $$C$$ is also a stable matching.

This is my attempt. I'm stuck at proving that there are no unstable pairs. By contradiction, let $$(m_1, w_1)$$ and $$(m_2, w_2)$$ be the unstable pair in $$C$$, i.e., $$m_1$$ prefers $$w_2$$ over $$w_1$$ and $$w_2$$ prefers $$m_1$$ over $$m_2$$. I think we have to consider two cases: when $$(m_1, w_1)$$ and $$(m_2, w_2)$$ happen in the same matching or in different ones, but I don't know what to do from here.

First, you need to prove that $$C$$ is a matching: suppose it is not a matching. That means that there exists two men $$m_1$$, $$m_2$$ matched with the same woman $$w$$.
It follows that, without loss of generality, $$m_1$$ is matched with $$w$$ in $$A$$ and $$m_2$$ is matched with $$w$$ in $$B$$. Without loss of generality again, suppose $$w$$ prefers $$m_1$$ to $$m_2$$.
Then it means that $$B$$ is not stable, because $$m_1$$ prefers $$w$$ to its partner in $$B$$, and $$w$$ prefers $$m_1$$ to $$m_2$$. We conclude that $$C$$ is indeed a matching.
Second, you need to prove that $$C$$ is stable: suppose it is not stable. Let $$(m_1, w_1)$$ and $$(m_2, w_2)$$ be the unstable pair in $$C$$, i.e., $$m_1$$ prefers $$w_2$$ over $$w_1$$ and $$w_2$$ prefers $$m_1$$ over $$m_2$$. WLOG, $$(m_1, w_1)$$ was a pair in $$A$$. Two cases are possible:
• either $$(m_2, w_2)$$ was also a pair in $$A$$ (can you see the contradiction?);
• or $$(m_2, w_2)$$ was a pair in $$B$$. Consider then $$w_3$$ such that $$(m_1, w_3)$$ is a pair in $$B$$. Again, can you see the contradiction? (what is the ranking of $$w_1$$, $$w_2$$ and $$w_3$$ for $$m_1$$?)