In the Gale–Shapley algotherim if men are proposing then it's man optimal but I'm having a hard time understanding the proof.
The proof:
We want to show that the algorithm assigns to each boy his most preferred eligible partner.
Suppose, in order to reach a contradiction, some boy is paired with someone other than his best eligible partner. Since boys propose in decreasing order of preference,some boy is rejected by an eligible partner. Let Lloyd be the first such boy, and let Amy be first valid partner that rejects him. When Lloyd is rejected, Amy must have available a boy, say David, whom she prefers to Lloyd.
Let M be the stable matching in which Amy and Lloyd are mates. Let Beth be David’s partner in the matching M. Now we can obtain a contradiction by showing that M is not a stable matching. By assumption, David was not rejected by any eligible partner at the point when Lloyd is rejected by Amy (since Lloyd is first to be rejected by an eligible partner). Thus, David prefers Amy to Beth. But Amy prefers David to Lloyd. The matching cannot M cannot be stable. This contradiction establishes the result.
Here a w is a valid partner of m if there is a stable matching that contains the pair (m, w).
Because Amy is a valid partner of Lloyd $\exists$ a stable matching M where (Lloyd, Amy) $\in M.$ But there should be no guarantee that in this new matching M Llyod is rejected but the proof just sort of assume that is the case. The way I see the proof there are sort of 2 worlds. The one where we Lloyd is rejected by Amy and another where the stable matching contains them as a pair. I don't see how the two worlds intersect.