How do I get (a) + (b) + (c) $\implies$ (d) $\implies$ (e)?
(a) Show that for each $m \in M$, if $\mu(m) = \emptyset$ for some stable matching $\mu$, then for the woman-optimal matching, $\mu_W$, $\mu_W (m) = \emptyset$.
Proof: Suppose for $m \in M$, $\mu(m) = \emptyset$ for some $\mu$ stable and that $\mu \neq \mu_W$. By definition $\mu_W$ gives $m$ his least preferred achievable partner. So we can conclude that $\mu \geq_m \mu_W \implies \emptyset \geq_m \mu_W$. But $\mu_W$ is stable so it must be individually rational, which means
$\mu_W(m) = \emptyset$
(b) $m \in M$, for the man-optimal set, $\mu_M$, if $\mu_M (m) = \emptyset$, then $\mu(m) = \emptyset$ for every stable matching $\mu$.
Proof: If for $m \in M$, $\mu_M(m) = \emptyset$, then $\emptyset$ is $m$'s best achievable partner since the matching is man-optimal. So for any other matching, $\mu'$, $\emptyset\geq_m \mu'(m)$. By individual rationality of stable matchings, it must be that $\mu'$ also assigns $m$ to $\emptyset$.
(c) Show that for every man $m\in M$, if $\mu(m) \in W$ for some stable matching $\mu$, then $\mu_M(m) \in W$. Similarly, show the same for the women.
Proof: If a stable matching $\mu$ sends $m$ to $W$, then $m$ prefers his partner in $W$ over $\emptyset$, and that partner is achievable. So now if we consider $\mu_M(m)$, we get the m-optimal matching, and $m$ gets his most preferred achievable mate. So this mate is achievable and at least as preferred as the mate in $\mu$ and therefore more preferred than $\emptyset$ so $\mu_M(m) \in W$ for $m$ also. The same argument can be said from a women's perspective by replacing the $m$'s and $M$'s with $w$ and $W$.
(d) using (a), (b), and (c) show that $$|\{m \in M : \mu_M(m) = \emptyset\}| = |\{m \in M : \mu(m) = \emptyset \mbox{ for some stable matching } \mu\}|$$
(a) If a man is single in some $\mu$, then he is single in $\mu_W$
(b) If a man is single in $\mu_M$, then he is single in any other $\mu$.
(c) If a man is not single in some $\mu$, then he is also not single in $\mu_M$.
(e) Show that the set of agents who are single is the same for every stable matching.
