*This article is part of Five of Euler's best. Click here to read the other four problems featured in this series, which is based on a talk given by the mathematician Günter M. Ziegler at the European Congress of Mathematics 2016.*

We'll start with a favourite problems of ours, which we have often
visited on *Plus* (we've even made a movie of it). In the eighteenth century citizens of the Prussian city of Königsberg (now Kaliningrad) had set themselves a puzzle. Königsberg was divided by a river, called the Pregel, which contained two
islands with seven bridges linking the various land masses. The puzzle
was to find a walk through
the city that crossed every bridge exactly once.

Can you find a path that crosses every bridge once and only once? Image: Bogdan Giuşcă.

Euler realised that this type of problem required a new way of thinking. In a letter he wrote to the Italian mathematician and astronomer Giovanni Jacopo Marioni Euler said,

*This question is so banal, but seemed to me worthy of attention
in that geometry, nor algebra, nor even the art of counting was
sufficient to solve it. In view of this, it occurred to me to wonder
whether it belonged to the geometry of position
which Leibniz had once so much longed for. And so, after some
deliberation, I obtained a simple, yet completely established, rule
with whose help one can immediately decide for all examples of this
kind, with any number of bridges in any arrangement, whether such a
round trip is possible, or not....*

By *geometry of position* Euler meant a geometry that isn't
concerned with precise measurements of lengths, angles or areas. It's
what's today called *topology*. In the Königsberg
problem the exact lay-out of
the city doesn't matter. The only thing that is important is how
things are connected. Bearing this in mind, you can turn the messy map
of the town into a neat network (also called a *graph*), with
dots representing land masses and links between them the bridges.

Transforming the problem. Image: Bogdan Giuşcă.

Euler made a crucial observation: if a path through this network is going to cross every link exactly once, then each node within the path must have an even number of links attached to it. That's because whenever you enter the node by one link, you need to leave it by another, so the node needs two links if you visit it once, four if you visit it twice, and so on. The only nodes that can have an odd number of links attached to them are the nodes where the walk starts and ends (if they are distinct).

This immediately tells us that the path we are looking for doesn't exist in the Königsberg problem. All nodes have an odd number of links attached to them. The beauty of this argument, as Euler suggested in his letter, is that it works for any network, no matter how large or complex. A path that crosses every link exactly once only exists if all, or all but two, nodes have an even number of links attached to them. The converse is also true (though Euler didn't deliver a rigorous proof for this): if all, or all but two, nodes have an even number of links attached to them, then a path that crosses every link exactly once exists.

Euler's thoughts about the Königsberg problem marked the beginning
of an area of maths called *graph theory*, which you might also
call *network theory*. And since we're surrounded by networks,
be they social network, transport networks, or the internet, network
theory plays an important part in modern mathematics (see here for articles about networks).

If you know Latin, you can read Euler's original paper on the bridges of Königsberg on the Euler archive.

### About this article

This article is part of Five of Euler's best. Click here to read the other four problems featured in this series, which is based on a talk given by the mathematician Günter M. Ziegler at the European Congress of Mathematics 2016.

Günter M. Ziegler is professor of Mathematics at Freie Universität Berlin, where he also directs the Mathematics Media Office of the German Mathematical Society DMV. His books include *Proofs from THE BOOK* (with Martin Aigner) and *Do I count? Stories from Mathematics.*.

Marianne Freiberger is Editor of *Plus*. She really enjoyed Ziegler's talk about Euler at the European Congress of Mathematics in Berlin in July 2016, on which this article is based.