# Gale Shapley - Everyone ends up with second choice of partner

So I was asked to prove (or not) whether, in gale shapley algorithm, everyone can end up married to their second partner of choice or not. I think not but then I am not able to come up with a proof.

Thanks! :)

Let us number the men $1,2,3,4$ and the women $a,b,c,d$ (the men propose to the women), with the following preferences: \begin{align*} &1\colon b \succ c \succ d \succ a & a\colon 1 \succ 2 \succ 3 \succ 4 \\ &2\colon b \succ a \succ d \succ c & b\colon 3 \succ 4 \succ 1 \succ 2 \\ &3\colon a \succ d \succ c \succ b & c\colon 2 \succ 1 \succ 4 \succ 3 \\ &4\colon a \succ b \succ c \succ d & d\colon 4 \succ 3 \succ 2 \succ 1 \end{align*} Let us trace the Gale-Shapley algorithm:
• Round 1M: $1,2$ propose to $b$; $3,4$ propose to $a$.
• Round 1W: $b$ accepts $1$; $a$ accepts $3$.
• Round 2M: $2$ proposes to $a$; $4$ proposes to $b$.
• Round 2W: $a$ accepts $2$, throwing $3$; $b$ accepts $4$, throwing $1$.
• Round 3M: $3$ proposes to $d$; $1$ proposes to $c$.
• Round 3W: $d$ accepts $3$; $c$ accepts $1$.