Eulerian Graphs
| Definition: A graph $G = (V(G), E(G))$ is considered Eulerian if the graph is both connected and has a closed trail (a walk with no repeated edges) containing all edges of the graph. |
| Definition: An Eulerian Trail is a closed walk with no repeated edges but contains all edges of a graph $G = (V(G), E(G))$ and return to the start vertex. A graph with an Eulerian trail is considered Eulerian. |
Essentially, a graph is considered Eulerian if you can start at a vertex, traverse through every edge only once, and return to the same vertex you started at. For example, let's look at the two graphs below:
The graph on the left is Eulerian. You can start at any of the vertices in the perimeter with degree four, go around the perimeter of the graph, then traverse the star in the center and return to the starting vertex. The graph on the right is not Eulerian though, as there does not exist an Eulerian trail as you cannot start at a single vertex and return to that vertex while also traversing each edge exactly once.
The Seven Bridges of Königsberg
The Königsberg bridge problem is probably one of the most notable problems in graph theory. The problem is rather simple at hand, and was taken upon the citizens of Königsberg for a solution to the question: "Find a trail starting at one of the four islands ($A$, $B$, $C$, or $D$) that crosses each bridge exactly once in which you return to the same island you started on."
For many years, the citizens of Königsberg tried to find that trail. It wasn't until a few years later that the problem was proved to have no solutions. First, let's redraw the map above in terms of a graph for simplicity. We will use vertices to represent the islands while the bridges will be represented by edges:
So essentially, we want to determine if this graph is Eulerian (and hence if we can find an Eulerian trail).
Determining if a Graph is Eulerian
We will now look at criterion for determining if a graph is Eulerian with the following theorem.
| Theorem 1: A graph $G = (V(G), E(G))$ is Eulerian if and only if each vertex has an even degree. |
Consider the graph representing the Königsberg bridge problem. Notice that all vertices have odd degree:
| Vertex | Degree |
|---|---|
| $A$ | $3$ |
| $B$ | $5$ |
| $C$ | $3$ |
| $D$ | $3$ |
But we only need one vertex to be of odd degree to rule a graph as not Eulerian, so this graph representing the bridge problem is not Eulerian. Hence, there is no solution to the problem. Now let's look at some other graphs to determine if they are Eulerian:
The graph on the left is not Eulerian as there are two vertices with odd degree, while the graph on the right is Eulerian since each vertex has an even degree. You can verify this yourself by trying to find an Eulerian trail in both graphs. You will only be able to find an Eulerian trail in the graph on the right.
Semi-Eulerian Graphs
| Definition: A graph $G = (V(G), E(G))$ is considered Semi-Eulerian if it is connected and there exists an open trail containing every edge of the graph (exactly once as per the definition of a trail). You do not need to return to the start vertex. |
| Definition: A Semi-Eulerian trail is a trail containing every edge in a graph exactly once. A graph with a semi-Eulerian trail is considered semi-Eulerian. |
Essentially the bridge problem can be adapted to ask if a trail exists in which you can use each bridge exactly once and it doesn't matter if you end up on the same island. Unfortunately, there is once again, no solution to this problem.
Determining if a Graph is Semi-Eulerian
A graph is semi-Eulerian if and only if there is one pair of vertices with odd degree. You can imagine this problem visually. Take an Eulerian graph and begin traversing each edge. Now remove the last edge before you traverse it and you have created a semi-Eulerian trail. Remove any other edges prior and you will get stuck. For example, let's look at the semi-Eulerian graphs below:
First consider the graph ignoring the purple edge. By definition, this graph is semi-Eulerian. Try traversing the graph starting at one of the odd vertices and you should be able to find a semi-Eulerian trail ending at the other odd vertex. Now by adding the purple edge, the graph becomes Eulerian, and it should be rather clear that when you traverse the graph again starting at the same vertex, that when you get to what was once the end vertex now has an edge taking you back to the starting point.