However, we never explicitly showed why it is guaranteed that putting every job with its

optimal candidate results in a pairing at all. Prove by contradiction that no two jobs can have the

same optimal candidate. $($Note: your proof should not rely on the fact that the propose$-$and$-$reject

algorithm outputs the job$-$optimal pairing.