Eulerian paths and graphs

An Eulerian path is a walk through all the edges of the graph, each one being used exactly once.
An Eulerian cycle is an Eulerian path which comes back to its starting point. An Eulerian graph is a graph which contains an Eulerian circuit.
This is as well in the unoriented graphs as in the oriented graphs.
This names comes from a problem posed by Euler in 1766.

The town of Koenigsberg is crossed by river Pregel which has two islands, linked by 7 bridges.
Is it possible to walk across all bridges, each exactly once, getting back home ?
Answer is no, as proved by the following theorem.

Euler theorem

A connected graph has an Eulerian path if and only if the number of vertices with odd number of edges is 0 or 2.
It has an Eulerian circuit iff it has only even vertices.

Proof

The condition is obviously necessary, as for each visited vertex, but the first and last ones, every time we enter from an edge, we must leave by another edge.

Let's prove that if a graph has two even vertices, there exist an Eulerian path connecting these points. And if no odd vertices at all it has an Eulerian circuit.
Suppose this is true for all graphs with less than N vertices and consider a graph with N vertices, having two and only two odd vertices A and B.
Starting from A, at every visited vertex we can leave this vertex, unless it is B and all vertices at B have been used. Then if all edges have been used, we have found an Eulerian path. Otherwise, the part of the graph not visited has at least one less vertex (B), and each connected part has only even vertices. Hence each one has an Eulerian circuit. By merging the visited path with all these circuits, we get an Eulerian path from A to B.

If the graph has no odd vertices, consider two adjacent vertices A and B and delete one edge connecting them. Then the graph has just two odd vertices (A and B) and there is an Eulerian path from A to B. Then an Eulerian circuit through the deleted edge.

Koenigsberg bridges

The graph has only vertices with 3 edges (each strand and the small island) or with 5 edges (the large island) that is 4 odd vertices.
The Eulerian walk is then impossible.

Application - draw in one strike

We may want to draw a figure in a single strike, without lifting the pen.
In the classical envellope problem Euler theorem gives at once the necessary start and end points :
the only ones with odd number of edges.

And similarily in even much more complicated drawings :

 

In case it is impossible, this shows how to modify the problem so it becomes possible (where to add/delete edges for instance).
Here the graph can be drawn in two strikes.
Generally, if a graph has 2n odd vertices, it can be drawn in n strikes.

 

Home Arithmetic Geometric Misc Topics Scripts Games Exercices Mail Version Franšaise Previous topic Next topic