Consider an execution of the Gale-Shapley algorithm in which n candidates are applying for n jobs. All the candidates have ranked all the companies from 1 to n and all the companies have ranked all the candidates from 1 to n. The candidates are proposing, and the companies are accepting or rejecting the proposals.

Consider the following statement: There is at most one applicant who gets their last choice. Either prove that this statement is correct or give a counterexample.