Proof of the Stable Matching Problem Looking at the document Fundamentals of Computing Series, The Stable Marriage Problem.

Theorem 1.2.3 - page 12:


  In a man-optimal version of stable matching, each woman has worst
  partner that she can have in any stable matching.


Proof:


  Suppose not. Let $M_0$ be the man-optimal stable matching, and
  suppose there is a stable matching $M’$ and a woman $w$ such
  that $w$ prefers $m = p_{M_0}(w)$ to $m' = p_{M'}(w)$ . But
  then $(m,w)$ blocks $M'$ unless $m$ prefers $p_{M'}(m)$ to 
  $w = p_{M_0}(m)$, in contradiction of the fact that $m$ has no
  stable partner better than his partner in $M_0$.


I'm having trouble visualizing the definition of the problem and the proof (what is the contradiction?).

First, what is the question implying?  From what I read and the fact that in most stable matching examples, all the women do not end up with the completely last person on their list ... So I'm a bit confused.

In the proof, here is what I am getting: in $M'$ we suppose $w$ prefers $m$ to $m'$.  But then if there is a stable matching containing $(m,w)$ this would leave $w$ with her worst partner and that is a contradiction.  Is this correct?

In addition, if $m$ did prefer $w'$ it would contradict that it is not his first pick ?

I'm new to computer science concepts so any help is appreciated.
The claim is not that every woman ends with the last man on her list. Rather, consider all stable matchings, and all partners of some woman $w$ in these stable matchings. Among them, pick the worst one (according to her view) $m$. Then in the man-optimal matching, $w$ is matched to $m$.

Now that you understand what they're trying to prove, read the proof again. (It couldn't have made sense before, because the claim as you stated it just isn't true.)