Prove that the Gale-Shapley algorithm terminates after at most $n^2 - n + 1$ proposals. How do you prove that the Gale-Shapley algorithm terminates after at most $n^2 - n + 1$ proposals by showing that at most one proposer receives his or her lowest-ranked choice?
 A: Assuming you are using the same number of proposers and acceptors (because all of your problems are this way):
If exactly one proposer (from now on man) gets his last choice woman, he will have proposed $n$ times.  The remaining $n-1$ men are able to propose a maximum of $n-1$ times so $$(n-1)(n-1)+n=n^2-2n+1+n=n^2-n+1$$
This is possible as Preferences for four ladies and four gentlemen where one proposer receives his/her lowest-ranked choice,... shows.
Per http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15251-f10/Site/Materials/Lectures/Lecture21/lecture21.pdf, the men always get thier most preferable stable matching. Likewise the women always get thier least stable pairing so if it does not matter who proposes, there is only one stable pairing of men and women for that list of preferences.
If there were two men (Adam and Bob) who are paired with their worst choice women, (Alice and Beth respectively), by this GS method then Adam and Beth and/or Alice and Bob would produce a stable pairing. This would mean that the dude would end up with someone he prefers.
This is trivial for 2.  For $n=3$, Charlie must be Christina's first choice or the other pairs would not be stable as her first choice would prefer her to their current partner.  If this is the case, the AB pairs would still be stable as Christina still prefers Charlie.
When we throw in David and Danielle so that $n=4$ or increase $n$ to an arbitrarily high number, the arrangment of new women and men (everyone except the A's and Bs) that make the A-A and B-B pairings stable, would make the A-B and B-A pairs stable. Therefore, via the proof by Gusfield and Irving, they would form instead.
To confirm this, make any stable scenario of preferences and pairs that has two men with their last choices, let the men introduce the women to swinging by switching partners, and determine if the new setup is stable (it will be).  
