# Euler Cycles and Paths in Graph

*Euler Path is a path in a graph which crosses every edge of a graph exactly once, while euler cycles is a euler path such a way that start point meets with the end point i.e on same vertex. A graph is called Eulerian if it contains Euler Cycle in it. If graph contains only Euler Path then it is called semi Eulerian.*

*For example in below graph there is eulerian path (A B ) ( B C) ( C E) ( E F) ( F A) (A E) because this path contains every edge of the graph exactly once, where (A B) ( B C) (C E) (E F) (F A) and ( A E) are the edges and A B C E F are vertices of graph.
*

*Euler Path*

*Following graph contains an Euler cycle F A B C E F, because start vertex and end vertex is same.*

*Condition for undirected graph*

**Euler Cycle: An undirected graph has Euler cycle if**

*All vertices with non-zero degree belong to single connected component.*

*All vertices must have even degree.*

*Eulerian Path : An undirected graph has Eulerian Path if *

*All vertices with non-zero degree belong to single connected component.**If zero or at most two vertices have odd degree and all other vertices have even degree.*

*Condition for directed graph*

*A directed graph has an eulerian cycle if following conditions are true. (Source: Wiki)
*

*All vertices with nonzero degree belong to a single strongly connected component.**In degree and out degree of every vertex is same.*

*A directed graph has an eulerian Path if following conditions are true. (Source: Wiki)*

*All vertices with nonzero degree belong to a single strongly connected component.**A directed graph has an Eulerian path if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree*.

*Here is another post related to*

*How to check whether a undirected graph is eulerian?*

*How to check whether a directed graph is eulerian?*

* Ref*:

*http://www.quora.com/How-do-I-find-an-Euler-Circuit-in-a-graph-in-linear-time*

*https://en.wikipedia.org/wiki/Eulerian_path*

## Leave a Reply