Eulerian Graph and One-Stroke Game

Eulerian graphs are classic concepts in graph theory. They come from the famous Seven Bridges of Königsberg problem. This problem is important in math history and has many uses in computer science, such as path planning and circuit design.

Since this is a basic chapter, we won’t go deep into code. The exact algorithm code and exercises will be covered in the graph theory part of the data structures chapter.

This article will focus on the definition of Eulerian graphs, the classic seven bridges problem, what are Eulerian paths and circuits, and tips to find an Eulerian path. You can also try the "one-stroke drawing" game on our site to understand it better.

One-Stroke Drawing Game

When I was a child, I played the "one-stroke drawing" game. The rule is to draw through all the points and edges in one go. You can pass a point more than once, but each edge must be used exactly once and cannot be repeated.

This website has a game panel for this one-stroke drawing game:

As a child, I just tried randomly, starting anywhere and seeing if I could finish. If not, I would start over.

Later, I found out this puzzle is a classic graph theory problem, and there is a method to solve it.

Here is the rule to solve the game:

• If every node has an even degree, you can start from any node and finish the one-stroke drawing. You will end up where you started.
• If exactly two nodes have an odd degree, you must start from one of these two nodes to complete the drawing.
• If neither of the above is true, you can’t finish the game.

In the game panel, you can see the degree of each node. Try to use these rules and see if they work 😃

Now, let's learn the graph theory behind this game: Eulerian graphs.

The Seven Bridges Problem

The idea of Eulerian graphs comes from the famous Seven Bridges of Königsberg problem in the 18th century. The city of Königsberg (now Kaliningrad) had a river dividing it into north and south, with two islands in the river. There were seven bridges connecting the north, south, and the two islands.

The question is: Can you find a route that starts at any region, crosses each bridge exactly once, and ends at the starting point?

We can turn this into a graph problem:

In this graph:

• Each area is a node
• Each bridge is an edge
• The question is: Is there a path that uses each edge exactly once and returns to the starting node?

Euler finally proved that there is no solution to the seven bridges problem.

Terminology

Based on the seven bridges problem, here are a few graph theory terms:

How to Check if a Graph is Eulerian

Undirected Graph

Directed Graph

Algorithm to Find Eulerian Path