## 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