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.

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.

These materials were originally designed for public engagement and do not require much formal mathematical knowledge beyond counting. Although the topic of graph theory is beyond the scope of many mathematics curricula, it is fairly accessible as the problems can be clearly understood visually (e.g. colouring, drawing paths). This resource aims to develop logical thinking and problem solving skills while introducing the participants to a new side of mathematics.

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 o Instructor guide
    • PowerPoint explaining the game (with presentation guide)
    • 4 Virus games
    • Simple examples
    • Design your own graph to win the game

This resource is available under a CC BY-SA 4.0 license and has been made available on TES Connect which hosts a range of lesson materials for early years, primary, secondary, and special needs teaching.

Go to view and download Graph Theory: Puzzles and Games on TES Connect

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