Gaming Graph Theory

The Seven Bridges of Königsberg is an important historical problem in mathematics, explored by Leonhard Euler in 1735, that laid the foundations of graph theory and topology.

The city of Königsberg in Prussia (now Kaliningrad, Russia) was set on both sides of the Pregel River, and included two large islands which were connected to each other and the mainland by seven bridges.

 Mathematically the problem can be stated like this:

Given the graph above, is it possible to construct a path (or a cycle – a path starting and ending on the same vertex) which visits each edge exactly once?

Euler proved that it was not possible. He proved that for the existence of what he coined “Eulerian trails”, it is necessary that no more than two vertices have an odd degree; this means the Königsberg graph is not Eulerian. Mathematically, if there are no vertices of odd degree, all Eulerian trails are circuits. If there are exactly two vertices of odd degree, all Eulerian trails start at one of them and end at the other. A graph that has an Eulerian trail but not an Eulerian circuit is called semi-Eulerian.

This type of mathematics can be quite abstract for students (and teachers) and most find it quite difficult even when presented in context of network optimization, railway systems, traffic flow, shortest path problems etc. 

One Touch Drawing by Ecapyc Inc. is a nice puzzle game on iOS that deals exclusively with Graph Theory. It could be a nice way to get students thinking about Graph Theory before the topic is introduced and then used as a context for discussion and problem solving to give the topic more meaning to students. I have only played the first few levels, the the difficulty ramps quite quickly. Recommended.