Cycle without using edges twice

Computing Eulerian cycles

Being a postman, you would like to know the best route to distribute your letters without visiting a street twice? This problem of finding a cycle that visits every edge of a graph only once is called the Eulerian cycle problem. It is named after the mathematician Leonhard Euler, who solved the famous Seven Bridges of Königsberg problem in 1736.

Hierholzer's algorithm, which will be presented in this applet, finds an Eulerian tour in graphs that do contain one.

Bridges of Königsberg ¹

Even (green) and odd degrees (red)

Eulerian graph

First cycle (blue)

Second cycle (green) and complete Eulerian cycle
(a - c - e - f - c - d - b - a)

Computing Eulerian cycles

The problem of finden Eulerian cycles was first discussed in the 18. century. In the city of Königsberg (Kaliningrad nowadays) there existed exactly seven bridges, and people wondered whether one could find a cycle or at least a tour that would cross each bridge exactly once. The same problem occurs with the "Haus vom Nikolaus", which asks for drawing a house without lifting the pencil.

In Mathematics, one uses the concept of graphs and calls the corresponding structure Eulerian cycles, named after Leonard Euler. One asks for a list of edges such that every edge of the graph appears exactly once in the list. If you end at the same node that you started, it is called an Eulerian cycle, otherwise an Eulerian path.

Eulerian graphs

Leonard Euler was able to determine the exact conditions for a graph to contain an Eulerian cycle or tour. Hereby, one has to distinguish between directed and undirected graphs:

Undirected graphs
An undirected graph contains at least one Eulerian cycle if all of its nodes have an even degree. This means that all nodes have to be connected by two, four, six, ... edges to other nodes. This becomes obvious by the following argument: For all nodes you need exactly two edges, one to reach it and one to leave it. If we visit the node more than once, we would consequently need a multiple. A graph that has this property is called Eulerian graph.

For an Eulerian path one can relax the above requirements. Exactly two nodes then have to have an odd degree. For both of these nodes, one edge remains at the end; therefore one has to leave one of them one more time and arrive at the other one more time. These two nodes will then be the start and end node of the Eulerian path. Such a graph is called semi-Eulerian.

Directed graphs
For directed graphs the requirements mentioned above still hold, one just has to furthermore distinguish incoming and outgoing edges. To do so, a node's degree is separated into its indegree and its outdegree. The indegree describes the number of incoming edges, while the outdegree yields the number of outgoing edges. In order for a directed graph to be Eulerian, besides the degree being even the indegree of each node has to equal its outdegree.

For semi-Eulerian graphs one additionally requires a start node with an extra outgoing edge and an end node with an extra incoming edge.

When returning to the bridges of Königsberg, we conclude that the corresponding graph has four nodes with odd degree (red), therefore no Eulerian cycle exists. However, if the graph fulfilled all requirements, Hierholzer's Algorithm would compute an Eulerian cycle or path.

Idea of the algorithm

The basic idea of Hierholzer's algorithm is the stepwise construction of the Eulerian cycle by connecting dijunctive circles. It starts with a random node and then follows an arbitrary unvisited edge to a neighbour. This step is repeated until one returns to the starting node. This yields a first circle in the graph. If this circle covers all nodes it is an Eulerian cycle and the algorithm is finished. Otherwise, one chooses another node among the cycles' nodes with unvisited edges and constructs another circle, called subtour. By choice of edges in the construction the new circle does not contain any edge of the first circle, both are disjunct. However, both circles must intersect in at least one node by choice of the starting node of the second circle. Therefore one can represent both circles as one new circle. To do so, one iterates the nodes of the first circle and replaces the subtour's starting node by the complete node sequence of the subtour. Thus, one inegrates additional circles into the first circle. If the extended cycle does include all edges the algorithm is finished. Otherwise, we can find another cycle to include.

In the case of an undirected, semi-Eulerian graph the algorithm starts with one of the two nodes with odd degree. In the directed case with the node with one additional outgoing edge. One of the subtours to be found will then not form a cycle, instead it will also be a path. When integrating this "subtour" into the circle one has to make sure that start and end node of this path also form start and end of the complete Eulerian path.

What now?

¹ By Bogdan Giuşcă under GNU Free Documentation License 1.2, cf. Wikimedia.

What is the pseudocode of the algorithm?

Input: Undirected graph G=(V,E), no or exactly two nodes have odd degree
Output: List of nodes in Eulerian cycle/path

BEGIN
    IF graph infeasible THEN END
    IF graph semi-Eulerian THEN
        start ← node with odd degree
    ELSE
        start ← arbitrary node
    subtour ← ∅
    tour ← {start}
    REPEAT
        start ←  node in tour with unvisited edge
        subtour ← {start}
        current = start
        DO
            {current, u} ← take unvisited edge leaving current
            subtour ← subtour ∪ {u}
            current ← u
        WHILE start ≠ current
        Integrate subtour in tour
    UNTIL tour is Eulerian cycle/path
END

How fast is the algorithm?

Where can I find more information about graph algorithms?

A last remark about this page's content, goal and citations