## Explaining Eulerian Paths

A popular tool of creative programmers and mathematicians is* graph theory*. The father of graph theory is arguably Leonard Euler who studied a now famous problem called the *7 Bridges of Konigsberg*. The problem involved crossing each of 7 bridges exactly once without any backtracking or swimming across the rivers - aptly named a *Eulerian path*. Here's is a map of the seven bridges.

Can you see a path that crosses each of these bridges exactly once? No, me either. Euler in fact proved that one does not exist in this case and **one wont exist in any case in which the number of vertices with odd degrees is not zero or two**. Let me explain... First lets reduce the above picture into something more simplistic. When you cross a bridge you travel from one land mass to another, so lets reduce all the relevant land masses to "nodes". These are shown in red dots below. Note that we are only really interested in land masses that are on either side of one of the seven bridges.

Now we need to add the different routes that you can take over the bridges. If there are multiple bridges that span the river between two land masses then we can use multiple paths/edges on our "graph". In the image below, the black lines indicate possible bridge-crossing paths.

Admittedly this looks a little messy so here a nicer version of the same thing without the background imagery and having the "vertices" labelled with letters for easier reference.

This picture represents an *undirected graph* that has 4 vertices and 7 edges between them. If you count the number of edges that each vertex "connects to" you will note A, C and D all have 3, whilst B has 5. The number of edge connections a node/vertex has is called the *degree *(or less often, the *valency*) of the vertex. It is a common measure of centrality in graph theory applications - e.g finding the most influential person in a social graph could be the person with the most connections. Here, we are trying to find a path in the graph that traverses each *edge *exactly once. (This is in contrast to a *Hamiltonian path* in which you attempt to visit every node/vertex exactly once.)

So back to Euler's theorem: it's provable that there is NOT a Eulerian path here because you need exactly zero or two vertices with odd degrees for such a path to exist and we have 4 nodes with odd degrees. So now you know. It may sound a little academic and irrelevant but it does have a habit of cropping up in discussion of many other famous graph theory problems.

For example, suppose that a postman has to deliver letters to the residents in all the streets of a village. Assume that the village is small enough for the postman to be assigned this task everyday. If the undirected graph that represents the street network of the village has a Eulerian path then this path gives rise to a handy route that the postman can use to deliver letters going through every street exactly once. Clearly, this is a desirable for the postman. Alternately, if no such Euler path exists then the postman may have to repeat some of the streets. This problem is called the *Chinese postman problem* in honour of a Chinese mathematician Meigu Guan who proposed this problem.

If that's piqued your curiosity here a puzzle for you whose solution depends on existence or absence of a *Hamiltonian path*.

*03 Jun 2010*
*Damien Wintour*

on 12 Aug 2010 at 9:35 am 1AnthonyThere is actually a simple practial application of this, surprisingly. Namingly fixing fishing nets.

Take a square grid and rip out a hole. In order to fix the net (with one continuous piece of rope) you need to cut addtional links out until you have exactly two three link nodes.