Log in to Mathigon

Google
Create New Account

Reset Password     

Share

Change Language

EnglishVietnamese

Send us feedback!

Please let us know if you have any feedback and suggestions, or if you find any errors and bugs in our content.

Sorry, your message couldn’t be submitted. Please try again!

Thanks for your feedback!

Reset Progress

Are you sure that you want to reset your progress, response and chat data for all sections in this course? This action cannot be undone.

Glossary

Select one of the keywords on the left…

Graphs and NetworksParties and Dating

Reveal All Steps

You have been invited to an extravagant birthday party. Including yourself and the host, there are ${hnd} people present.

In the evening, as 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 , and every handshake 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 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 .

${handshakeTable(n)}

Unfortunately this answer is not quite right: we have counted every handshake , once for each of the two people involved.

For example, the first two entries on the top row are actually the same. 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×n12 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?

In this case, the corresponding graph consists of two separate sets of vertices. Every vertex is connected to all the vertices in set, but none of the vertices in set. Graphs which have this layout are called bipartite graphs.

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