I am a high school student self-studying for the Olympiad and came across this question in the book Challenge and Thrill of Pre-College Mathematics:
Prove that in any party the number of people who made an odd number of handshakes is always even.
I managed to ascertain some sort of proof, but it seems very heuristic rather than formal.
My attempt:
Clearly if two people shake hands, then we can say that each person experiences one handshake, which brings the total sum of experienced handshakes up to $2$. Building on this we can say that if there were $n$ handshakes then the number of experienced handshakes is $2n$.
At this point I remembered that I had read somewhere that these sort of questions can be answered using graph theory, which makes my statement equivalent to proving that the sum of the degrees of each node of a graph has to be even.
I think it is possible to say that since for each edge drawn there are $2$ nodes which each gain a degree, the sum of the degrees should be twice the number of edges, which implies that the number of edges is always even.
Thus if there so happens that there is an odd number of people who have experienced an odd number of handshakes, by parity the total number of experienced handshakes will be odd, which contradicts the above assertion, rendering the statement wrong.
Furthermore, I stumbled across this question in a number theory chapter, and the book itself does not have any chapter about graphs. Thus, I have two questions:
(1) How do I write the above proof, and (2) is there some number theoretic way to prove it?
Best Answer
Your proof looks good. In fact, you can skip the two middle paragraphs of your attempt and just use the first and the last. The total number of experienced handshakes is even, and therefore the number of people who experienced an odd number of handshakes must also be even. No need to mix graph theory into that answer.
The number theory behind this is that the sum of an odd number of odd numbers is odd. So this is a number theoretical proof.