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

Euler Cycles and Paths in GraphEuler Cycle

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

Euler Cycles and Paths in GraphCondition for undirected graph

Euler Cycle: An undirected graph has Euler cycle if

  1. All vertices with non-zero degree belong to  single connected component.
  2. 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)

  1. All vertices with nonzero degree belong to a single strongly connected component.
  2. 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

 



Related Contents to follow