Graphs and NetworksHandshakes and Dating

Rather than counting all the edges in large graphs, we could also try to find a simple formula that tells us the result for any number of guests.

Each of the ${n} people at the party shakes hands with ${n-1} others. That makes ${n} × ${n-1} = ${n×(n-1)} handshakes in total. For n people, the number of handshakes would be n×n−1n×n+1n2.

Unfortunately this answer is not quite right. Notice how the first two entries on the top row are actually the same, just flipped around.

In fact, we have counted every handshake twiceoncethree times, once for each of the two people involved. This means that the correct number of handshakes for ${n} guests is ${n}×${n-1}2=${n*(n-1)/2}.

The handshake graphs are special because every vertex is connected to every other vertex. Graphs with this property are called complete graphs. The complete graph with 4 vertices is often abbreviated as K4, the complete graph with 5 vertices is known as K5, and so on.

We have just shown that a complete graph with n vertices, Kn, has n×n−12 edges.

On a different day, you are invited to a speed dating event for ${m} boys and ${f} girls. There are many small tables and every boy spends 5 minutes with each of the girls. How many individual “dates” are there in total?

The bipartite graph with two sets of size x and y is often written as Kx,y. It has x×yx+y2x−y edges, which means that in the above example there are ${m} × ${f} = ${m×f} dates.