Last updated

27 February 2024

This resource is a set of worksheets about games and puzzles based on simple concepts in graph theory. The resource covers: the seven bridges of Konigsberg, the Shannon Switching game and graph vertex colouring. The resource is aimed at a general public level as formal mathematical knowledge is not required beyond counting, but younger audiences would need more guidance.

This resource aims to provide a very basic introduction to graph theory. The activities are designed to get participants to become familiar with how problems can be simplified into graph theory problems and how that may be used to find solutions.

In this resource:

• Graph Colouring: solving scheduling and allocating problems using graphs
• Instructor guide
• 4 Party Problems
• Rivers and Bridges: based on the Bridges of Konigsberg problem
• Instructor guide
• Matching activity
• Worksheets for 4 real cities (including Konigsberg)
• Shannon Switching game: a simple game which is played on a graph
• Instructor guide
• PowerPoint explaining the game (with presentation guide)
• 4 Virus games
• Simple examples
• Design your own graph to win the game

This resource was originally developed for the Edinburgh International Science Festival with the School of Mathematics.

Authors: Francesca Iezzi, Ana McKellar, Lukas Cerny, Benedetta Mussati and Patrick Kinnear (with
additional input from other members of the Maths Outreach Team), adapted for wider audiences by Ana
McKellar.

Unless otherwise stated, all content (including original images) is released under a CC BY-SA 4.0 license.

Cover image is Four Color Problem by Jeff Kubina (Flickr) is licenced under CC BY-SA 2.0.

Creative Commons "Sharealike"

### Reviews

5

Something went wrong, please try again later.

#### rossana_mastrandrea

2 years ago
5

Very interesting material to introduce and explain the use of graph theory to solve problems :) Thank you!

#### SarahDeller

5 years ago
5

A brilliant resource to illustrate applications of graph colouring.

#### dsc505

5 years ago
5

An awesome resource for introducing some of the ideas of graph theory to students. Thanks!

#### sbatllor

5 years ago
5

Very complete resource. Thank you!

Report this resourceto let us know if it violates our terms and conditions.
Our customer service team will review your report and will be in touch.