# Handshake problem, each person can have 5 handshakes

There are a total of $60$ handshakes in a party. Each person can only shake hands with $5$ other people. So, how many people are there? Is the answer $24$?

A group of $6$ is formed. One group can have $1+2+3+4+5=15$ handshakes. $60/15=4$ Hence, number of people is $4\times 6= 24$.

• If a person doesn't have to shake hands with five others, but is allowed to do fewer, then there could be more people. For instance, if everyone shakes hands with only one other person, then there are $120$ people. So $24$ is only the correct answer if each person must shake hands with exactly $5$ other people. – Arthur Jun 22 '17 at 8:39

There are many ways to arrange the graph with 60 edges and having each vertex of degree five. You simply chooses two edges from different subcliques in your graph and delete current edges and cross-connect their ends (replace edges $(a,b),(c,d)$ with $(a,c),(b,d)$ ), what you get is a graph with the same number of edges and vertices and same vertex degrees, but different from your original graph. And you can repeat this step many times to create a lot of different graphs.