The streets of a small village are modeled as a graph, like the one shown to the right.
The post car has to drive through all streets every day. Is it possible to find a route that
covers every street (edge) exactly once? This is called an **Eulerian Tour**.
If the tour starts where it started, it is called **closed**, otherwise
**open**. A graph is called **Eulerian**
if it allows a closed or open Eulerian tour.

See the famous "house of the Nicolaus" as an example.

We face two problems:

- How can we recognize Eulerian graphs?
- Even if we know that a given graph is Eulerian, i.e. allows an Eulerian tour, how do we find this tour?

The first problem has to do with the degrees of the vertices. Assume we have an Eulerian tour in a graph. Consider any vertex x that is not the start vertex. At the beginning, all d(x) edges incident with x are untraveled. After having visited x the first time, and having left, two of these edges incident with x have been traveled so far, thus there remain d(x)-2 untraveled edges incident with x. Note that we have to return to x as long as there are untraveled edges incident with x, since we are assuming we are travelling an Eulerian tour. This continues, until eventually we have 1 or 2 untraveled edges incident with x, depending on whether the degree d(x) of x is odd or even. In the first case, as soon as we return to x, we have to stop there. Thus in this case x must be the end vertex of the tour. Thus, if an Eulerian tour is possible, all vertices of odd degree must either be the start or the end vertex of that tour. Therefore, at most 2 of such vertices of degree 2 are possible.

For example, look at the following graphs and test which of them has a Eulerian tour:

Actually we didn't prove the whole theorem yet, just that the condition is necessary. We will show sufficiency of the condition algorithmically, providing an algorithm (called "EULERTOUR") that finds an Eulerian tour if the two conditions are satisfied. This addresses also the second problem mentioned above. We have to describe an algorithm simple enough that every five-year old, when sticking to it, would succeed in finding such a Euler tour. Let's begin with an obvious one, which however, as we will see, will not always be successful.

- either no odd-degree vertex, and x=y any vertex, or
- exactly two odd-degree vertices x and y.

- Find some vertex z on the tour with some of its incident edges not traveled by the tour yet.
- Use algorithm JUSTGO, starting on z and using only edges not traveled by the tour considered yet, to find a tour going back to z.
- Insert this detour in the existing tour at z.

Therefore, for every graph with at most two verteces of odd degree, every non-Eulerian tour starting on the right vertex (on a vertex of odd degree if that exists) can be extended. Thus eventually we will have found our Eulerian tour.

- Find a first incomplete tour, using JUSTGO.
- As long as the tour is not Eulerian yet (doesn't visit all edges), increase the size of the tour using ADDLOOP.

A special case of this problem---whether or not it would be possible to travel through Königsberg and cross each of the seven bridges exactly once--- was solved by the Swiss mathematician Leonhard Euler (1707-1783) in 1736. He not only solved the simple special case, but also provided the general theorem below and started a whole branch of mathematics, which nowadays is called Graph Theory.

Euler spent his life working in The Russian Academy of Sciences in St Petersburg (1727-1741), and at the Academy in Berlin (1741-1766), and was called back to St Petersburg by Catherine the Great in 1766.

- .............

- Which one of the three graphs below has an Eulerian tour?
If there is one, is it open or closed?

- Which one of the graphs below has an Eulerian tour?
If there is one, describe it by giving the sequence of vertices visted.

- Every morning the lazy postman takes the bus to the post office. Starting there,
he arranges his route so that he ends at home to go back to sleep as quickly as possible.
Below is a map of the streets along which he must deliver mail,
giving the number of minutes required to walk each street,
whether delivering or not. P denotes the post office and H denotes home.
Source

Which edges have to be traversed more than once in an optimal route (i.e. a shortes tour from P to H containing all edges)? - Let a graph have all three digit numbers from 0 to 999 (including those with leading zeros, like 000, 001, 002, ... 010, 011, ... as vertices. Two such vertices are adjacent if they share at least one digit at the same position (example 132 and 038 are adjacent). What is the degree of a vertex in the graph? Is the graph Eulerian?
- Let a graph have all three digit numbers from 0 to 999 (including those with leading zeros, like 000, 001, 002, ... 010, 011, ... as vertices. Two such vertices are adjacent if they share two digits at the same position (example 138 and 038 are adjacent). What is the degree of a vertex in the graph? Is the graph Eulerian?