293 views
What are the necessary and sufficient conditions for Euler path and Circuit in directed graph?
| 293 views

+1 vote

Euler Path:

1.If the graph is connected and has exactly 2 odd degree vertices then there exists at least one Euler Path.Mainly it starts with one end and ends on the other End.

Euler Circuit:

1.If the graph is connected and every vertex has even degree then the Graph has atleast one Euler Circuit.

Euler Circuit is a part of Euler Path but Converse is nt True.

 # of ODD Vertices Implication (for a connected graph) 0 There is at least  one Euler Circuit. 1 THIS IS IMPOSSIBLE! 2 There is no Euler Circuit but at least 1 Euler Path. more than 2 There are no Euler Circuits or Euler Paths.
by Active (3.7k points)
–1
These are for undirected graph,right? I need for directed graph
+1

Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.

A directed graph has an eulerian cycle if following conditions are true.
1) All vertices with nonzero degree belong to a single strongly connected component.
2) In degree and out degree of every vertex is same.

Euler Path -->> If a graph is weakly connected or is w/o repetition of edges and

Indegree= outdegree for all except for two vertices. One out of those two has indegree = outdegree+1. Other has  indegree+1 = outdegree.

Euler Circuit -->>   If a graph is weakly connected or is w/o repetition of edges and

Indegree= outdegree.
by Junior (883 points)

1
2