Euler Graph

Definition

Let $G$ be a connected graph. If there exists a closed trail that includes all edges of $G$, then $G$ is called an Eulerian graph, and the trail is called an Eulerian trail. If there exists a trail that includes all edges but is not closed, then $G$ is called a semi-Eulerian graph.

Explanation

This concept is also familiar to us as the problem of drawing with one stroke.

The discussion about the Eulerian graph started with the famous Seven Bridges of Königsberg problem. The problem was whether it is possible to cross all 7 bridges laid out in the city only once and return to the initial position.

$Konigsberg\_bridges.png$ If you don’t know the solution, at first glance, it seems like a daunting problem that requires checking every possible case. It doesn’t even appear to be a mathematical problem at first, and while it seems like it could be solved by checking all cases, it’s not easy to do so.

The great mathematician Euler beautifully solved this by turning it into a graph problem. It’s astonishing because this solution came at a time when graph theory was not even the focus of academic interest, and the idea of looking at spaces topologically did not exist. In other words, Euler brought future concepts to solve a problem with future methods.

The following is the theorem that demonstrates the necessary and sufficient condition for a graph to be an Eulerian graph.

Theorem ¹

Let $G$ be a connected graph.

$G$ being an Eulerian graph is equivalent to all vertices of $G$ having even degrees.

Proof

$(\Rightarrow)$

$P$ is an Eulerian trail of $G$. $P$ has to pass through two edges attached to any vertex it passes. Since every edge is included in $P$ only once, the degree of each vertex becomes the sum of $2$. Therefore, all vertices must have even degrees.

$(\Leftarrow)$

Auxiliary Lemma: If all vertices of a finite graph $G$ have a degree of $2$ or more, then $G$ contains a cycle.

Since all vertices of $G$ have even degrees, they have degrees of $2$ or more, and thus, it is guaranteed that there exists a cycle $C$ in $G$. If all edges of $G$ belong to $C$, there’s nothing to prove. Now consider the graph $H = G \setminus C$ obtained by removing only the edges passed by cycle $C$. Although $H$ has lost a cycle $C$ and thus may have lost connectivity, since only $2$ edges are reduced per vertex, the degrees remain even. Moreover, each component of $H$ has at least one vertex in common with cycle $C$. Following the same method for each component by finding and removing new cycles until a null graph is formed, and let’s denote the sequence of these cycles by $\mathcal{C}_{k}$. Since these cycles necessarily share vertices with previously found ones, it’s possible to traverse all cycles, thus a trail that covers all edges exists, making $G$ an Eulerian graph.

■