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.