Euler, Konigsberg and WW2
Recently I taught a D1 lesson introducing the terminology involved in graph theory. Looking at trees, networks and all the other associated things. Graph theory is something I love. I never studied the decision modules at A level, so when I arrived at Manchester University in the autumn of 2001 and saw the module title: “Trees and Networks – with Professor Nigel Ray” I was intrigued by the name, but entirely unsure as to what it would contain. I loved every minute of that course, and have loved graph theory ever since. I’m certain that Nige’s inspirational lecture style deserves some of the credit, but I’m also fairly sure that graph theory itself deserves some credit too.
As you may or may not know, graph theory (sometimes called topology) is an area of maths which was built by Leonhard Euler (Oi! Read that name again, its pronounced “Oi-ler” not “you-ler”… don’t ever let me catch you making that mistake again….). Euler was prompted to discover this area of maths by the “Seven bridges of Konigsberg” Problem. In brief: The city of Konigsberg in Prussia (Now called Kaliningrad and in Russia) was dissected by the Pregel so that there are 4 distinct parts of the city. There were seven bridges, as shown below, and the problem was posed: was it possible to take a walk round the city traversing all the bridges once and only one?
Euler solved the problem. Of course he did, he was a total maths legend. Although by solved, I don’t mean he worked out a way to do it (or that he built an extra bridge), but rather he managed to prove that it could not be done. Something many had thought, but had been unable to prove beyond doubt. It was his method of analysis and proof that led to Graph Theory. All this, and my general love of all things Eulerian, meant that I digressed in my D1 lesson away from terminology and spend a lot of time discussing Eulerian graphs, semi-Eulerian graphs, Konigsberg and Euler himself. Not exactly what I was supposed to cover, but time well spent none the less.
The following day, I read this amazingly funny piece by Colin Beveridge (@icecolbeveridge) on Flying Colours Maths, and the two related articles that it linked to (this and this). I was excited, I could see the bridges on street view (although only two remain from Euler’s Time) so finally got to see (some of) the bridges that this area of maths was devised for! I was surprised to discover that since WW2 there are only 5 bridges, leaving the network traversable! (It is now semi-eulerian, you must start on one island and end on the other. So if you were to do it properly you would need to get to your start and from the finish point on a boat or other none bridge means). And I was happy to hear that google themselves use graph theory to find the best routes for their streetview cars! (Incidentally, I’m on streetview, sat in a bus shelter in LS1 –or at least I used to be…)
These two events (teaching D1 and Colin’s post) have reawakened my love for graph theory, and I’m looking to widen my knowledge of this wonderful area. If you’ve read anything good on it do let me know! First stop: Nige’s Lecture Notes!