A tricky subset counting problem The problem is: A group of people met and some of them (NOT all of them) shook each other hands. Prove that the number of people who shook others' hands an odd number of times is even. My attempt: 1. I have already shown the cardinality of the group of people must be finite, since saying infinity is even doesn't make sense. 2. I tried to use the method of graph theory. But I encountered a critical problem that "the member of people who shook others' hands an odd number of times" can shook hands with "the member of people who shook others' hands an even number of times". I thought the condition was "all of them shook each other hands", which is a easy case. But this one seems harder. I cannot figure it out. Any help will be appreciated.

You mentioned using the methods of graph theory so I'll assume you are somewhat familiar with graph theory terminology. This question is equivalent to the question: Prove that the number of odd degree vertices of a finite graph is even. Now there is a close relationship between the _sum_ of the degrees of the vertices of a graph and the number of edges of that graph. Do you see what it is? What does it tell you about the number of odd degree vertices?