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.
 A: If there exists $n$ people, then each person can shake hands with $n-1$ others. Each handshake gets counted twice. So ....
A: 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}$.
A: 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...
A: 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}.$$
A: 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.
A: 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. 
A: 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.


*

*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.

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

*Proof at wiki article above.

*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.

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

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

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

*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.
