Definition

An Euler graph (or Eulerian graph) is a graph in which there exists a closed walk that visits every edge exactly once. This specific closed walk is called an Eulerian Circuit or Eulerian Cycle.

Origins

Most people have probably heard of the famous Seven Bridges of Königsberg problem. If not, please read about it on Wikipedia or below.

The city of Königsberg (now Kaliningrad, Russia) was situated on both banks of the Pregel River and included two large islands connected to each other and the mainland by seven bridges.

The challenge is to devise a path that starts from one landmass, crosses each bridge exactly once, and returns to the starting point.

Why is this problem important?

This problem is important because this marks the origin of Graph Theory. So, let us think what sequences of bridges we can choose to device the required walk?

Leonhard Euler proved that it is impossible to devise such a path for this particular scenario and this was the beginning of Graph Theory. He pointed out that the choice of route inside each land mass is not actually important. The only important thing is the sequence of bridges crossed.

Another version of this problem : Draw a figure without lifting your pencil from the paper and without retracing any of the paths.

These kind of puzzles are all over and can be easily solved by Graph Theory.  Such a closed walk running through every edge exactly once,  if exists then the graph is called a Euler Graph and the walk is called a Euler path or Euler line.

Characteristics of an Eulerian Graph

  1. Even Degree: In an Eulerian graph, every vertex has an even degree (i.e., each vertex has an even number of edges connected to it). This property is necessary and sufficient for the existence of an Eulerian Circuit in an undirected graph.
  2. Connected Graph: The graph must be connected, which means there is a path between any pair of vertices in the graph. Note that for an Eulerian Circuit, the connectedness specifically pertains to every vertex having edges.
  3. Eulerian Circuit: An Eulerian Circuit is a cycle that starts and ends at the same vertex and visits every edge of the graph exactly once.

How to determine if a Graph is a Euler Graph?

Euler proved a graph is an Euler Graph if and only if all its vertices have an even degree.

Proof

If a graph G is an Euler Graph, it has a closed walk tracing all edges exactly once. At any vertex, there are at least two edges not yet traversed—one to enter and one to leave. The vertex that is both starting and ending will have one incoming edge, so each vertex must have an even degree.

This proof shows that having an even degree is a necessary condition. To fully prove it, we must show it’s also a sufficient condition.

Proof of Sufficiency

Assume graph G has all vertices with even degree. Start a walk from vertex v, tracing as many edges as possible without revisiting any. Since all vertices have even degrees, we can enter and exit each vertex, ending the walk at v.

Two scenarios arise:

  • If all edges are traversed, G is an Euler Graph.
  • If only a subset of edges is traversed, call this subset G’ and remove G’ from G, forming graph H. i.e. H = G - G'
    • H will also have all vertices with even degrees since G had even degrees and G’ was an Eulerian path.
    • Since G is connected, H must touch G at least once, say at vertex u.
    • Start a walk from u in H, tracing edges once and ending at u.
    • Combine G’ and H to form a longer walk, which is an Eulerian path.
    • If all edges in H are traversed, H is an Euler Graph.
    • Otherwise, repeat the process until an Eulerian path using all edges is found.

Here is a diagram to illustrate this visually.

Conclusion

We learned that Euler Graphs and Eulerian Paths are fundamental yet easily understandable topics. These concepts are useful for solving many basic puzzles. To be an Euler Graph, the necessary and sufficient condition is that all vertices must have an even degree.

Stay tuned and happy learning!