Graph Theory: Puzzles and Games
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
3 Radio 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.