Theorem 8: Eulerian circuits

On several occasions over the last few weeks, I have read that Immanuel Kant was from the Prussian city of Königsberg (now Kaliningrad in Russia).  As a mathematician, this is not the first thing that comes to mind when I think of Königsberg. Instead, I think of the famous seven bridges (no longer all there), and the mathematical problem that they inspired.  Let me tell you about that problem, and about some of the interesting mathematics that came out of it.

Like many cities, Königsberg was situated on a river.  The city included an island in that river, and so there were several bridges, between the island and the banks of the river.  There’s a picture of the city and its bridges on Wikipedia.

So what was the problem?  Well, could a resident of Königsberg have gone for a Sunday afternoon stroll in such a way that he would walk over each bridge exactly once? That is, he had to cross every bridge (no doubling back!), but he wasn’t allowed to walk across any bridge more than once. (No ferries allowed either!)  Oh, and our friendly Königsberger wanted to end up at home, where he started.

The problem was first solved by the great Swiss mathematician Leonhard Euler.  What did he do?  His first step was to strip away the extraneous information so that he could focus on the important things.  Today, we are familiar with his idea, thanks to the map of the London underground, but of course that came much later than Euler.  The idea is the same, though: what matters is not geographical locations, but which places are joined to which other places.  We can represent lumps of land (the island and the banks of the river) by blobs (vertices, singular vertex), and bridges by lines connecting those blobs (edges).  Here’s what Königsberg looks like when represented in this way (by a graph).

Now the problem is to decide whether we can draw this network of edges without taking the pen off the paper (and without drawing any edge more than once).  You might like to try this before reading on.

So, did you manage it?  I bet you didn’t!  But can you prove that it’s not possible?  That’s what Euler did.

What goes wrong when you try to draw it?  I think that the problem is probably that you find yourself stuck at a vertex with no way out (but with an edge still to draw).  Is that inevitable?  Let’s think about what happens at some vertex A (not the starting vertex).  We go in to it.  Then we go out again.  Then, perhaps a bit later, we go in.  Then …  In fact, every time we go in to it, we want to leave it again.  So we need an even number of edges at that vertex.  A similar argument shows that we need an even number of edges at the start/finish vertex too.  (The number of edges at a vertex is called the degree of that vertex.  We’ve just said that we need all the vertices to have even degree.)

What happens in Königsberg?  Well, there are three vertices with degree 3, and one with degree 5.  In particular, they all have odd degree.  So there can’t possibly be a path of the sort we want (an Eulerian cycle)!

That’s the Königsberg problem pretty much wrapped up.  As mathematicians, though, we’d like to know more.  We’d like to generalise.  Here, we had quite an easy way to show that the walk wasn’t possible (we just checked each vertex to see whether it had even degree, and as soon as we found one that didn’t we knew that there couldn’t be an Eulerian cycle).  What would happen for a different graph (configuration of lumps of land and bridges)?  If all the vertices have even degree, does that mean that an Eulerian cycle exists, or just that we can’t use this method to rule out the existence of one?  Well, let me tell you what this week’s theorem says.

Theorem A connected graph has an Eulerian cycle if and only if every vertex has even degree.

Remember that the degree of a vertex is the number of edges coming out of it.  A connected graph is one in which it’s possible to get from any vertex to any other vertex: there are no isolated components.  A graph that isn’t connected can’t possibly have an Eulerian cycle, because there are two vertices with no path between them (two bits of land that aren’t connected by any route).  So we have to make sure that we deal only with connected graphs.  But that’s not a big problem, because any graph that isn’t connected is still made up of connected components, so we can just think about those instead.

We’ve already see the justification of one direction of this result.  Let’s remind ourselves.  If there’s an Eulerian cycle, then we have to go out of each vertex as many times as we go into it.  So each vertex must have even degree.

What about the other direction?  That’s a bit more interesting, because it’s not quite as easy to prove (although it’s not terribly difficult).   One proof is by induction on the number of edges in the graph.  That is, one shows that it’s true when there are no edges (not very difficult!), and then one shows that if it’s true for all graphs with edges, then it must also be true for all graphs with edges.  In the interests of keeping this post to a reasonable length, I’m not going to go into the details, but you’re welcome to ask below if you want me to say some more.

Euler’s work is often seen as the start of the branch of mathematics called graph theory, which is a good source of interesting theorems and questions (although it took a while for it to get started after Euler’s work).   These days, it also has some applications, for example to computer science and the theory of networks (such as the internet).  That said, as a pure mathematician my main interest is in the maths for its own sake!  The famous four colour theorem (perhaps a future theorem of the week?) belongs to graph theory, to give just one more example.