#eulerian cycle

I have to confess that I don’t really know, if childeren in other countries play this game, but in Germany we draw the “house of Saint Nicholas”. And children are saying the syllables

“Das-ist-das-Haus-vom-Ni-ko-laus.”

(Translation: “This-is-the-house-of-Ni-cho-las.”)

for each line they draw, while they draw a house in the way which is shown above. The only rules are the following:

1.) You have to draw the lines without lifting the pen.

2.) You have to draw "complete” straight lines .

There are several ways to do this.

Graph theory sayes something about the existence of drawing such an object. In Graph theory we consider a bunch of vertices which are connected with edges (lines). The Graph for the “Haus vom Nikolaus” is shown in the picture.

The way of drawing the house described above is called an Eulerian trail, i.e. a value of the form

  v1 e1 v2 e2 v3 ... e(n-1) v(n)

where e1,...,e(n-1) are the edges and v1,...,vn are the vertices. Such a value has the special property as an Eulerian trail that we go no edge twice or more times.

We also need to know the degree of a vertex. The degree of a vertex is the number of edges which lead to this vertex. For example the degree of the edges of the “Haus vom Nikolaus” is shown in the picture.

One can show the following: If the degree of all edges is even, then there exists an Eulerian cycle, i.e. an Eulerian trail which starts and ends at the same vertex. An Eulerian trail (which is not an Eulerian cycle) exists, if the degree of two edges is odd and the degree of the other edges is even.

If we consider the graph of the “Haus vom Nikolaus”, we see that we have two edges of odd degree (3) and three edges of even degree (2 and 4). So we have an Eulerian trail which is not an Eulerian cycle. This means, that we can draw the “Haus vom Nikolaus” considering the rules described above.

Another interesting object is the problem of the Seven Bridges of Königsberg (1736). You can find a graph decribing the problem. With the rules we formulated above for an Eulerian trail, you can easily check, if it is possible to find a way over the 7 bridges without going a bridge twice or more times. Here is the link of this interesting historic problem which Euler solved: