\problemdata     
{computation-6}           
{Mating algorithm}              
{}              
{S02 in-class Week 5} 		
{S02 Meyer}        	


\begin{problem}
Prove that the Mating Algorithm produces stable marriages.  (Don't look up
the proof in the Course Notes.)

\solution{\begin{proof}
Let Bob be some boy and Carole some girl that he does \emph{not} marry on
the last day of the Mating ritual.  We will prove that Bob and Carole are
not a rogue couple.  Since Bob was an arbitrary boy, it follows that no
boy is part of a rogue couple.  Hence the marriages on the last day are
stable.

To prove the claim, we consider two cases:

\emph{Case} 1.  Carole is not on Bob's list.  Then since invariant $P$
holds, we know that Carole prefers her husband to Bob.  So she's not going
to run off with Bob: the claim holds in this case.

\emph{Case} 2.  Otherwise, Carole is on Bob's list.  But since Bob is not
married to Carole, he must have chosen to serenade his wife instead of
Carole, so he must prefer wife.  So he's not going to run off with Carole:
the claim also holds in this case.
\end{proof}}

\end{problem}
