# General Solution to Hand-Shaking Counting Problem

Okay, perhaps this is a really stupid question but it has been puzzling me for a long time. I am preparing GRE general test, and in every test preparing book, there is also a counting question of shaking hands.

I have encountered the following two questions:

In a room of 10 people, each people need to shake hands with exactly 3 people, what is the total number of handshakes? (Shaking hand with oneself does not count.)

For this question, the solution is just $$\frac{3\times 10}{2}=15$$. Basically it lets each one to shake hands with three people, and then it double counts since A shaking hands with B means B shaking hands with A as well.

Another version of question is that:

In a room of 10 people, if each person shakes exactly once with others, what is the total number of handshakes? (Again shaking hand with oneself does not count.)

This has a general formula: if the room is of $$n$$ people, then the total number of hand shakes is $$n(n-1)/2$$.

These kind of questions really puzzle me, since it seems no general solution for them. For example, what if in a room $$10$$ people, I want each people to shake hands with exactly $$2$$ people? what if $$5$$ people? what if the room is of $$n$$ people?

There have been some posts in the stack exchange, but what I have seen are individual cases. Is it possible for a general formula? For example, in a room of $$n$$ people, shaking hands exactly with $$k$$ people?

Thank you!

## 1 Answer

This can be generalized even more. If you have $$n$$ people, $$p_1, p_2,..., p_n$$ and you want $$p_i$$ to shake hands with $$a_i$$ people, then do the follwoing:

Make a graph in which every vertex is a person and draw an adge between any 2 people that shake hands. Observer that $$deg(p_i)=a_i$$, $$\forall i$$, so the number of handshakes, i.e. the number of edges is $$\frac{\sum_{i=1}^{n}deg(p_i)}{2}=\frac{\sum_{i=1}^{n}a_i}{2}$$

Important: for the handskaes to be possible, $$\sum_{i=1}^{n}a_i$$ must be even.

So to answer your question, if we have $$n$$ people and each should shake hands with $$m$$ people, for this to be possible $$mn$$ must be even and we have $$\frac{\sum_{i=1}^{n}a_i}{2}=\frac{mn}{2}$$

(because $$a_1=a_2=...=a_n=m$$)