"In a party people shake hands with one another"

In a party people shake hands with one another (not necessarily everyone with everyone else).
(a) Show that 2 people shake hands the same no. of times.
(b) Show that the number of people who shake hands an odd no. of time is even.

I find this question to be very tough and I can't find a way to even start answering this. It would be great if I could get a small hint in order for me to at least start it.

Solution 1:

Hints:

For (A) with $n$ people at the party, what are the possible number of hands each person could shake?

Show that it is impossible for both someone to have shaken hands with everyone and someone to have shaken hands with noone simultaneously.

Is there some way to use the pigeon-hole principle here?

For (B) count the number of handshakes that occur by adding up how many handshakes people participated in individually and recognize that this overcounted somehow (because each handshake we counted twice: once from the shorter person of the two and again from the taller person). This gives us a useful result called "the handshaking lemma."

What happens then if there are an odd number of people who shook an odd number of hands? Remember that the number of handshakes must be a whole number.

Solution 2:

$(a)$ Say that there is $n$ people in the party and assume everyone shakes hands at least once. The number of handshakes possible for everybody then is just $n-1$ (self-handshaking doesn't count) while there is $n$ people in the party, so the pingeon-hole principle gives the desired result. Now, if we don't assume that everyone shakes at least one hand then we can separate the $n$ people between $k$ which don't shake any hands and $m$ which do ($k+m=n$), and the problem is reduced to the last case (with $n=m$).

$(b)$ If a person $A$ shakes hands with a person $B$, then $B$ shakes hands with $A$. Silly as it sounds this tells us that we can count handshakes in pairs, so the total number of handshakes must be even. Counting separately the handshakes of those who have given an even number of handshakes and those who have given an odd number of handshakes leads to the desired conclusion.

Solution 3:

For (B) try induction. What happens when the next two people shake hands?