I am using w for the woman and m for the man.

Suppose such a rejection occurs. Consider the first such rejection. This means w rejects m because some m' higher on her priority list proposes to her later. Say, in the stable matching S where w was paired with m, m' was paired with w'. Since w prefers m' to m, the matching must have been stable because m' prefers w' to w. So in the algorithm, m' must have proposed to w' first and got rejected. Therefore we get a contradiction to our initial assumption.

The second part is obvious.