Eulerian Graph and One-Stroke Game

An Eulerian graph is a classic topic in graph theory, first found in the famous Königsberg Bridge Problem. This problem is important in math history and has many uses in computer science today, such as route planning and circuit design.

This is a basic section, so we won’t discuss code in detail. The code and exercises will be covered in the data structure chapter about graphs.

This article will focus on the definition of Eulerian graphs, the classic bridge problem, the concepts of Eulerian path and circuit, and tips for finding Eulerian paths. You can also try these ideas in the related one-stroke puzzle game on this website.

One-Stroke Puzzle

I remember playing the "one-stroke" puzzle as a kid. The rule is: draw a line through all points and edges in one stroke. You can visit a node more than once, but each edge must be used exactly once and cannot be reused.

We have this puzzle as a mini-game on the website, too:

When I was little, I played this game by luck, just picking a starting point and walking randomly. Sometimes I could finish, sometimes not, then I would restart.

Later, I learned that this puzzle is an example of a classic graph theory algorithm, and there are clear methods to solve it.

Here are the simple rules to solve this puzzle:

• If all nodes have even degrees, you can start from any node and finish the puzzle, ending at the starting point.
• If exactly two nodes have odd degrees, you must start from one of these nodes to finish the puzzle.
• If neither of the above is true, you cannot finish the puzzle.

In the game panel, the degree of each node is shown. Try the above rules to see if they help solve the puzzle 😃

Now, let’s talk about the graph theory behind this puzzle — Eulerian graphs.

The Bridge Problem

Eulerian graphs come from the famous Königsberg Bridge Problem in the 18th century. At that time, the city of Königsberg (now Kaliningrad) had a river splitting it into north and south. There were also two small islands, with seven bridges connecting the north, south, east island, and west island.

The question was: can you design a path that starts anywhere, crosses every bridge exactly once, and returns to the starting point?

We can turn this into a graph problem:

In this graph:

• Each region is a node
• Each bridge is an edge
• The problem is: is there a path that goes through every edge exactly once and ends up at the starting point

Euler finally proved by math that the bridge problem cannot be solved. This was a famous result.

Terminologies

Based on the bridge problem, let’s introduce a few graph theory terms:

How to Tell If a Graph Is Eulerian

Undirected Graph

Directed Graph

How to Find an Eulerian Path