Exercise $6\mathrm{.}3.[10$pts$]$ There are $n$ people who can shake hands with one another $($where $n>1).$ Use pigeonhole principle to show that there is always a pair of people who will shake hands with the same number of people.

Hint. Pigeonhole principle does not immediately apply to this problem. Solve the problem for two cases:

$(1)$ There is no person who shakes hands with everyone else $($all handshake numbers are strictly less than $n-1.$ Easy case.

$(2)$ There is a person who shakes hands with everyone else $($handshake number is $n-1).$ What can you say about handshake numbers for everyone else?

$1$