# Graphs and NetworksHandshakes and Dating

You have been invited to a wonderful birthday party with your friends. Including yourself and the host, there are

In the evening, as the guests get ready to leave, everyone shakes hands with everyone else. How many handshakes are there in total?

We can represent the handshakes using a graph: every person is

Now it is easy to count the number of edges in the graph. We find that there with ${hnd} people, there are ${hnd*(hnd-1)/2} handshakes.

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, the number of handshakes would be

Unfortunately this answer is not quite right. Notice how

In fact, we have counted every handshake

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

We have just shown that a complete graph with

On a different day, you are invited to a speed dating event for

In this case, the corresponding graph consists of two separate sets of vertices. Every vertex is connected to all the vertices in **bipartite graphs**.

The bipartite graph with two sets of size *x* and *y* is often written as