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.