# Understanding the Handshake Problem

I need help with this problem. The problem goes like this: In some countries it is customary to shake hands with everybody in the meeting. If there are two people there is 1 handshake, if there are three people there are three handshakes and so on. I know that the formula is $\dfrac{n(n-1)}{2}$ but how do I get to this solution using a thinking process, specifically how would you solve this? Thanks.

-

There are $n$ people who can shake hands with $n - 1$ other people. Since two people shake hands at once, we really count twice as many handshakes as we should since one handshake is counted twice. So, we divide by $2$ to remove redundancy. By the product rule, this gives us $$\frac{n(n-1)}{2} \text{handshakes}.$$

-
Or you can say we're only considering half the population because they'll shake hands with the other half. – Nick Dec 29 '13 at 5:26
@Nick I'm not sure what this comment means. If you say "half the room shakes hands with the other half", you fail to count any of the handshakes that could occur within either of the two halves. – Austin Mohr Dec 29 '13 at 5:34
@Austin: hehe, didn't consider that. But how would you define the formula without saying that we're "halving the number of handshakes so that they're not double counted"? I mean there's got to be another perspective, right? – Nick Dec 29 '13 at 15:10
@Nick Perhaps there's another perspective, but I don't know of a simpler one. The technique of overcounting is ubiquitous in combinatorics, so it's best to become familiar with it. – Austin Mohr Dec 29 '13 at 20:26

There's generalization for undirected graphs http://en.wikipedia.org/wiki/Handshaking_lemma

Here are few ways you can think about this or ways that can give you more insight.

1. If there are $n$ people. The first person makes $n - 1$ handshakes, the second $n - 2$ ... the last one $0$ so we have to calculate the sum $n + (n-1) + (n-2) + ... +0$ and well you know this sum.

2. Matrix representation by Adjacency matrix. In undirected graph the matrix has diagonal symmetry.

3. Proof at wiki article above.

4. Mathematical induction thinking. Like for example you construct the graph add one vertex (with only edges connecting vertices that are already) there at the time and see that invariant stated in handshaking lemma stays true.

5. Writing down some graphs and marking the two ends of each edge (like for example dashes or 1 symbols) can give you more intuition.

6. You can try to imagine graphs in 3D to give you more insight.

7. You can play in mind with some graphs and try to count edges.

8. Add new Guard vertex in the "middle" of the graph and then change every edge in a way that instead of edge (V1)(V2) I have two edges (V1)(Guard) (Guard)(V1) and also I mark these two edges like this

• (V1)-V1-----V2-(G)-V1-----V2-(V2)

That way graph becomes planar (the edges doesn't cross) . And you kind of see the same graph structure + it is more clear that each original edge has two ends.

And of course the ways other people mentioned and well there are for sure many more.

-

Here's a more mechanical way to look at it. We can use the binomial coefficient to express the same result. The notation $\binom{n}{k}$, pronounced "$n$ choose $k$," is the number of ways that a set of $k$ objects can be chosen from $n$ objects in total. It can be shown that the formula for calculating it explicitly is

$$\binom{n}{k} = \frac{1}{k!} \cdot \underbrace{n(n-1)\cdots (n-(k-1))}_{k \text{ factors}}.$$

In this situation, we're trying to find the number of ways that two people can be chosen from the group of $n$ people. There are $\binom{n}{2}$ ways to do this, or, using the above formula, $\frac{1}{2}n(n-1)$ handshakes.

-

Another take on the getting the same formula:

Rank the $n$ people in some defined way: age, salary, whatever.

Top person gets handshakes from $n-1$ people younger/poorer paid than him/her.

Next in the ordering gets $n-2$ handshakes from those "beneath" him/her, and so on. Last person gets $0$ handshakes from underlings.

What is the sum of all the integers from $0$ to $n-1?$

Really just another way to avoid double counting...

-

If there exists $n$ people, then each person can shake hands with $n-1$ others. Each handshake gets counted twice. So ....

-

Hint: Start with one person out of the $n$ persons, he handshakes $(n-1)$ persons. Follow with any other and remember that you already shook hands with the first person.

-
To deform this question a bit. What if we had $n$ people in a room, each person is only allowed to shake the hands of $k$ other people. What is the total number of handshakes? $\large\frac{n\cdot k}{2}$ – Nick Dec 29 '13 at 5:28
Not quite. For $n=5$ and $k=3$ for instance, you only get 7 handshakes. The last guy only shook hands with two people. Unless the formula you pointed truncates. – Doktoro Reichard Dec 29 '13 at 7:28

What you can do is induction : You want to know that, if there are $n$ people at meeting, there will be $$\frac{1}{2}n(n-1)$$ handshakes.

You have already established this for $n=2$, so suppose it is true when $n=k-1$, and you want to establish it for $n=k$. Now you know that, with $k-1$ people in the room, there are $$\frac{1}{2}(k-1)(k-2)$$ handshakes. If 1 person enters the room, he/she shakes hands with each person in the room, adding $(k-1)$ handshakes to the total. This gives $$\frac{1}{2}(k-1)(k-2) +(k-1) = (k-1)\frac{(k-2) + 2}{2} = \frac{1}{2}k(k-1)$$ handshakes.

Thus, by induction, you have established it for all $n\in \mathbb{N}$.

-
I'm not sure this really answers the OP's question, which seems more about "how would I find this formula from scratch?". This answers "how would I prove it is correct once it's given to me?" – Erick Wong Dec 29 '13 at 5:06