Traversability of Networks (Durchlaufbarkeit von Netzen)

I panicked the other day when my ten year old son, as part of his homework, asked me about traversing graphs.  Even worse, the following day, he was to have a test and was supposed to be able to determine if one could travel along every edge of a given graph only once without lifting the pencil from the paper after having started and whether or not it was possible to end up at the starting point.

When it is possible to do so, then the graph is said to contain an Euler cycle or circuit and is often referred to as an Eulerian graph after the famous Swiss mathematician Leonhard Euler, who dealt with such puzzles while solving the famous Seven Bridges of Königsberg problem in 1736.

If it’s possible to traverse over every edge only once but not end up at the starting point, then the graph is said to contain an Euler trail or path.

The rules for determining whether a graph has an Euler circuit, Euler path or neither, is unsolveable, can be summed up as follows:

For Euler circuits, or Eulerian graphs, every node or vertex of the graph must be of an even degree (the degree of a vertex is counted by the number of edge, which are connected to it).

For graphs that only have a path but no circuit, there can only be two odd vertices present. The presence of one, three or more odd vertices means that it is not possible to completely traverse the graph and only travel along each edge once and only once.

Euler Circuit (ending at beginning node)
One can start at any node. All the nodes are of even degree. Click on the nodes below to traverse the graph. Clicking twice on a node will undo the last move.

Euler Path (traverse graph but not end up at the starting node)
Exactly two of the vertices are odd. One must start at one of the odd vertices and end up at the second one.

Not traversable or impossible 

One, three or more than three of the nodes are of odd degree.