What is Euler Circuit?
A circuit that visits every edge of a graph exactly once is known as Eulerian Circuit or Eulerian cycle. It starts and ends at the same vertex. A graph may contain multiple Euler Circuits. If the graph is directed then Euler circuit is defined as a directed cycle that visits each edge exactly once.
A graph that contains a Euler Circuit is known as Euler Graph.
Euler Circuit Examples
Criteria for Euler Circuit
Theorem
A connected graph contains an Euler circuit if and only if every vertex has even degree.
Proof
Suppose a connected graph containing an Euler circuit. The Euler Circuit begins with a vertex x. Each time the circuit enters a vertex, it must leave via another edge. Basically, each pass through a vertex contributes 2 to its degree. Thus, the degree of each vertex is even. Circuit terminates where it starts. The circuit must enter vertex x again. Thus, the degree of vertex x is also even.
We just showed if a graph contains an Euler circuit then the degree of each vertex is even. The converse is also true.
Theorem
If the degree of every vertex in a connected graph is even, then it contains an Euler circuit.
Proof
The proof is intuitive, if all vertices have even degree then for every edge going into a vertex, there exists another edge leaving that vertex. Thus, the circuit can never get stuck. There must exist a circuit that visits every edge exactly once.
Thus, we can conclude that a connected graph contains an Euler circuit if every vertex have even degree.
Note: If the graph is directed, then Euler circuit exists if the in-degree of every vertex is equal to its out-degree.
What is Euler Path?
A path that visits every edge of a graph exactly once is known as Euler Path. It is also known as Eulerian Trail or Eulerian Walk. If the graph is directed, then Euler path is defined as a directed path that visits each edge exactly once.
A graph that contains Euler Path but no Euler Circuit is known as Semi-Euler Graph.
Note: Every Euler circuit is an Euler path but every Euler path is not an Euler circuit. Euler path may start and end on different vertex.
Euler Path Examples
Criteria for Euler Path
Theorem
A connected graph contains an Euler path and not an Euler circuit if and only if it has exactly 2 vertices of odd degree.
Proof
Suppose a connected graph G containing an Euler Path P. For every vertex v, other than starting and ending vertex, the path P must enter and exit the vertex the same number of time. In simple words, the degree of v should be even. If vertex v has an odd degree, then it is impossible to visit all edges of v without revisiting edges.
We can conclude that every vertex except the first and last vertex of P have even degree.
Let a and b be the first and last vertex of Euler path such that a and b are unique ( Euler path is not a circuit ).
Suppose the degree of a is even. The path starts from a. Even degree means for every edge going out of a, there exist an edge entering a. If we visit all edges connected to a, then we will end up getting stuck on vertex a.
Suppose the degree of b is even. The path ends at b. Using the same argument as above, even degree means for every edge going into b, there exists an edge leaving b. Thus, the path can never end at b.
Thus, we can conclude that a connected graph contains an Euler path if it contains exactly 2 or no vertices with odd degree.
Applications
Euler circuits and Euler Paths can be used in road transport networks, in connecting utility grids, traversing every street in the neighborhood. A mailman can find the Euler circuit of a town and delivery mails without going through a road twice. Eulerian circuit is used in the construction of de Bruijn sequences.
Read
References
Eulerian path